파이썬 백준 11049 행렬 곱셈 순서

import sys
input = sys.stdin.readline
 
n = int(input())
M = []
for i in range(n) : 
    M.append(list(map(int, input().split())))
 
max = sys.maxsize
DP = [[max for i in range(n)] for i in range(n)]
for i in range(n) : 
    DP[i][i] = 0
for len in range(1, n) : 
    for i in range(n) : 
        if i + len < n : 
            for cut in range(len) : 
                DP[i][i + len] = min(DP[i][i + len], 
DP[i][i + cut] + DP[i + cut + 1][i + len] + M[i][0] * M[i + cut][1] * M[i + len][1])
 
print(DP[0][n-1])

(line 17은 너무 길어 두줄로 표시했다. line 17, 18은 원래 코드에서는 한줄이다.)

 

IDEA

2개의 행렬 AB을 곱하는데 필요한 연산 수는 최대와 최소가 없다. 그냥 곱하면 된다.

그러므로 3개 이상의 행렬을 곱할 때에는 그 행렬곱을 두개의 행렬로 쪼개어 생각한다.

3개의 행렬 ABC를 곱하는데 필요한 최소 연산 수는 (AB)C와 A(BC)중에 작은 것이다.

4개의 행렬 ABCD를 곱하는데 필요한 최소 연산 수는 A(BCD), (AB)(CD), (ABC)D중에 작은 것이다.

즉 BCD, AB, CD, ABC같은 부분행렬의 최소연산수를 안다면, ABCD의 최소연산수를 알 수 있다.

일반화하면, 길이 n-1 이하의 모든 부분행렬곱의 최소연산수를 안다면 n 행렬곱의 최소연산수를 알 수 있다.

즉 길이가 작은 부분행렬곱부터 DP table을 채워나간다면 답을 구할 수 있다.

table을 채워나가는 순서

점화식으로 표현하면 아래와 같다.

f(ABCDE) = min(f(A) + f(BCDE) + cost of A*(BCDE), f(AB) + f(CDE) + cost of (AB)*(CDE), ... )

 

line 10 ~ 20

DP[i][j]는 전체 행렬에서 i번째부터 j번째까지를 곱하는데 드는 최소연산수이다.

예를들어 DP[0][2] = f(ABC)이고, DP[2][3] = f(CD)이다. IDEA대로 DP table을 채워나간다.

둘로 나눈 부분행렬곱의 f는 이미 기록되어 있으니 table로부터 가져오면 된다.

두 부분행렬곱의 결과물을 곱하는데 필요한 비용은 (맨 왼쪽 행렬의 행 * 나눈 기준선의 왼쪽 행렬(cut)의 열 * 맨 오른쪽 행렬의 열)이다. (line 18)

table을 완성 후 전체 행렬의 결과물 DP[0][n-1](0번째부터 n-1번째까지 곱한 최소계산수)을 출력한다.