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

Answer

import sys
input = sys.stdin.readline
n = int(input())

a = [list(map(int, input().split())) for _ in range(n)]
dp = [[0] * n for _ in range(n)]

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

        for k in range(j, e):
            dp[j][e] = min(dp[j][e], dp[j][k] + dp[k + 1][e] + a[j][0] * a[k][1] * a[e][1])


print(dp[0][-1])