백준 | [파이썬 Python] 11049 행렬 곱셈 순서

 

---

문제

 

 

코드

import sys
input = sys.stdin.readline

n = int(input().strip())

matrices = []
for _ in range(n):
    r, c = map(int, input().split())
    matrices.append((r, c))

dp = [[0] * n for _ in range(n)]

for length in range(1, n):
    for i in range(n - length):
        j = i + length
        dp[i][j] = float('inf')

        for k in range(i, j):
            cost = dp[i][k] + dp[k + 1][j] + matrices[i][0] * matrices[k][1] * matrices[j][1]
            if cost < dp[i][j]:
                dp[i][j] = cost

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

 

 

설명

앞 선 11066 파일합치기를 참조하면 3번째 for문을 통해 cost가 만들어지는 과정을 알 수 있다

그리고 또 하나의 알고리즘인 행렬 곱셈

위 비용을 계산식이 뒷쪽 matrices로 곱해주었습니다

 

예시