백준 11049번: 행렬 곱셈 순서 (Python) TODO

문제

크기가 N×M인 행렬 A와 M×K인 B를 곱할 때 필요한 곱셈 연산의 수는 총 N×M×K번이다. 행렬 N개를 곱하는데 필요한 곱셈 연산의 수는 행렬을 곱하는 순서에 따라 달라지게 된다.

예를 들어, A의 크기가 5×3이고, B의 크기가 3×2, C의 크기가 2×6인 경우에 행렬의 곱 ABC를 구하는 경우를 생각해보자.

• AB를 먼저 곱하고 C를 곱하는 경우 (AB)C에 필요한 곱셈 연산의 수는 5×3×2 + 5×2×6 = 30 + 60 = 90번이다.
• BC를 먼저 곱하고 A를 곱하는 경우 A(BC)에 필요한 곱셈 연산의 수는 3×2×6 + 5×3×6 = 36 + 90 = 126번이다.

같은 곱셈이지만, 곱셈을 하는 순서에 따라서 곱셈 연산의 수가 달라진다.

행렬 N개의 크기가 주어졌을 때, 모든 행렬을 곱하는데 필요한 곱셈 연산 횟수의 최솟값을 구하는 프로그램을 작성하시오. 입력으로 주어진 행렬의 순서를 바꾸면 안 된다.

입력

첫째 줄에 행렬의 개수 N(1 ≤ N ≤ 500)이 주어진다.

둘째 줄부터 N개 줄에는 행렬의 크기 r과 c가 주어진다. (1 ≤ r, c ≤ 500)

항상 순서대로 곱셈을 할 수 있는 크기만 입력으로 주어진다.

출력

첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같다.

 

---

 

풀이

dictionary로 memoization하며 재귀적으로 풀었는데, 시간 초과가 나서 인터넷에서 풀이를 보았다.

D := (N+1) by (N+1) matrix where D[i][j] == "i번째 행렬에서부터 j개의 행렬을 곱하는 최소 횟수"

정의상 D[i][j] == 0 when i, j 0 or 1이며,

D[i][j] = min(D[i][j-k] + D[i+j-k][k] + "i번째부터 i+j-k-1번째 행렬까지 곱한 행렬과 i+j-k번째 행렬부터 i+j-1번째 행렬까지 곱한 행렬 2개를 곱하는 횟수")가 된다.

 

TODO: 조금 더 깔끔하게 적기

 

 

코드

import sys, collections


N = int(sys.stdin.readline())
size = list(map(int, sys.stdin.readline().split()))
for _ in range(N-1):
    size.append(int(sys.stdin.readline().strip().split()[-1]))
matrix_num = len(size) - 1
dp = [[0]*len(size) for _ in range(len(size))]

if matrix_num == 1:
    print(0)
else:
    for j in range(2, matrix_num+1):
        for i in range(1, matrix_num+2-j):
            dp[i][j] = min(dp[i][j-k] + dp[i+j-k][k] + size[i-1] * size[i+j-k-1] \
                            * size[i+j-1] for k in range(1, j))

print(dp[1][N])