알고리즘 - Python / 백준 - 11049번 : 행렬 곱셈 순서

11049번: 행렬 곱셈 순서 (acmicpc.net)

11049번: 행렬 곱셈 순서

 

---

풀이

• DP 문제 중 유명한 문제인 행렬 곱셈 순서 문제다.
• 행렬의 곱셈 순서 문제를 작은 문제 단위로 나누었을 때 , 이전 단계의 문제가 다음 문제를 푸는데 도움을 준다.
• 따라서 DP를 사용해 풀 수 있다. 예를 들어 M1 * M2 * M3 * M4의 경우 M1 * M2 / M2 * M3 / M3 * M4 곱을 먼저 구하였다면 , 이후 M1 * M2 * M3 / M2 * M3 * M4의 경우에도 위에서 구한 값을 사용할 수 있다.
• 따라서 위의 경우를 통해 가장 적게 계산을 반복하는 경우를 DP 배열에 저장하고 마지막에 출력하면 된다. 

 

import sys
n = int(sys.stdin.readline()); s=[];
dp_s = [[0 for _ in range(n+1)] for i in range(n+1)]

for i in range(0,n):
    a,b = map(int, sys.stdin.readline().split(" "))
    s.append(a)
    if i == n-1:
        s.append(b)

for d in range(1,n):
    for i in range(1,n-d+1):
        dp_s[i][i+d] = float("inf")
        for k in range(i,i+d):
            if dp_s[i][k] + dp_s[k+1][i+d] + s[i-1] * s[k] * s[i+d] < dp_s[i][i+d]:
                dp_s[i][i+d] = dp_s[i][k] + dp_s[k+1][i+d] + s[i-1] * s[k] * s[i+d]
print(dp_s[1][n])

---