구간을 잡아야하는 matrix chain multiplication 다이나믹 프로그래밍

11049번: 행렬 곱셈 순서

 

n*m인 행렬과 m*k인 행렬을 곱하면 n*k인 행렬이 나오고 연산량은 n*m*k이다

 

A의 크기가 5*3, B의 크기가 3*2, C의 크기가 2*6인 경우 ABC를 곱할때

 

(AB)C를 곱하면 AB를 곱해서 5*3*2번, AB는 5*2행렬이고, AB와 C를 곱해서 5*2*6 = 총 90번

 

A(BC)를 곱하면 BC를 곱해서 3*2*6번, BC는 3*6행렬이고 A와 BC를 곱해서 5*3*6 = 총 126번

 

행렬의 크기 r*c가 n개 주어진다.

 

이 n개의 행렬은 곱할 수 있다고 할때, 최소 연산량을 구한다면?

 

--------------------------------------------------------------------------------------------------------------------------------------

 

dp[i][j] = i번 행렬부터 j번 행렬까지 곱했을때 가능한 최소 연산량이라고 정의

 

사실 그동안 푼 문제와는 좀 달라서 이것부터 생각하기 좀 어렵다

 

이제 구간의 길이를 1,2,3,..,n까지 늘려가면서,

 

각 구간의 길이마다 시작점 i = 0,1,2,...를 잡아가며 테이블을 채우면 된다.

 

길이를 알고 시작점을 알면 끝점 j = i + length - 1

 

구간의 길이가 1인 경우 즉 i = j인 경우는 dp[i][i] = 0이다. 

 

왜냐하면 행렬 하나있으면 곱하는게 없기 때문

 

이제 구간의 길이가 length이고 i ~ j = i+length-1까지 곱한다고 할때,

 

어떻게 곱할 수 있을까? 예를 들어 생각해보자

 

i번 i+1번을 곱하고, i+1번~j번을 곱한 다음 두 행렬을 곱할 수 있다

 

혹은 i,i+1,i+2,..,i+5번을 곱하고, i+6번,...,j번을 곱한 다음 두 행렬을 곱할 수 있다

 

혹은 i,i+1,...,i+10번을 곱하고, i+11번,...,j번을 곱한 다음 두 행렬을 곱할 수 있다

 

혹은 i,i+1,i+2번을 곱하고 i+3,i+4,...,j번을 곱한 다음 두 행렬을 곱할 수 있다

 

혹은 i+1,i+2,...,j번을 곱한 다음 i번 행렬과 곱할 수 있다

 

혹은 i,i+1,...,j-1번을 곱한 다음 j번 행렬과 곱할 수 있다

 

...

 

즉 i~j사이 어떤 지점 k = i,i+1,...,j-1에 대하여 i~k번까지 곱한 행렬과 k+1 ~ j번까지 곱한 행렬을 곱하는 방법이 있다

 

현재 구간 길이보다 작은 길이의 곱셈량 dp[i][k], dp[k+1][j]는 이미 구해져있기 때문에 이를 이용할 수 있다

 

i ~ j 사이에 있는 지점 k = i,i+1,...,j-1에 대하여

 

i부터 k까지의 곱 dp[i][k]이고, i~k까지 곱한 행렬의 크기는 (i번 행렬의 행 * k번 행렬의 열)

 

k+1부터 j까지의 곱 dp[k+1][j], k+1~j까지 곱한 행렬의 크기는 (k+1번 행렬의 행 * j번 행렬의 열)

 

이때 k번 행렬과 k+1번 행렬은 곱할 수 있기 때문에 k번 행렬의 열 = k+1번 행렬의 행

 

따라서 두 행렬을 곱하면 i번 행렬의 행 * k번 행렬의 열 * j번 행렬의 열만큼의 연산량이 추가로 필요하다

 

그러므로 dp[i][j] = dp[i][k] + dp[k+1][j] + (i번 행렬의 행 * k번 행렬의 열 * j번 행렬의 열)

 

from sys import stdin

n = int(stdin.readline())

A = []

for _ in range(n):
    
    r,c = map(int,stdin.readline().split())
    A.append((r,c))

INF = 10**23
dp = [[0]*n for _ in range(n)] #dp[i][j] = i~j번 행렬끼리의 곱의 연산량 최솟값

#구간의 길이
#길이가 1인 경우는 곱하지 않으므로 0
for length in range(2,n+1):
    
    #구간의 시작점
    for i in range(n-length+1):
        
        j = i + length - 1 #이러면 i ~ j까지는 길이가 length

        dp[i][j] = INF #초기값
        
        #i~k까지 곱 dp[i][k], A[i][0]*A[k][1]
        #k+1 ~ j까지 곱 dp[k+1][j], A[k][1]*A[j][1]
        
        for k in range(i,j):
            
            dp[i][j] = min(dp[i][j],dp[i][k] + dp[k+1][j] + A[i][0]*A[k][1]*A[j][1])

print(dp[0][n-1])