(백준) 11049. Matrix Multiplication Order – Python

(골드 III)

https://www.acmicpc.net/problem/11049

설명

(백준) 10942. Palindrome? – 파이썬(백준) 9252. LCS 2 – 파이썬(백준) 7579. 앱 – 파이썬

최근 풀린 위의 세 가지 DP 문제와 크게 다르지 않은 문제.

하지만 DP가 DP라는 것을 알더라도… 서로 다른 상황에서 각각의 문제에 대한 해결책을 제시하기가 쉽지 않습니다.

그리고 28행에서 i += 1

이거 잊고 30분 찾았는데……

자세한 설명은 댓글로 대신합니다.

N = int(input())

mat = ()

for _ in range(N):
    r, c = map(int, input().split())
    mat.append((r, c))

# NxM 행렬과 MxK 행렬을 곱하면, NxMxK.
# dp(i)(j)는 i+1번째 행렬부터, j+1번째 행렬까지 곱했을 때의 곱셈 연산 횟수의 minimum.

# k = i ~ j-1 사이의 임의의 값일 때,
# dp(i)(j) = dp(i)(k) + dp(k+1)(j) + mat(i)(0)*mat(k)(1)*mat(j)(1) 의 값들 중 최소값.
dp = ((0)*N for _ in range(N))

for i in range(N-1):
    dp(i)(i+1) = mat(i)(0)*mat(i+1)(0)*mat(i+1)(1)

for L in range(2, N):
    i = 0
    j = L

    while j < N:
        dp(i)(j) = 2**31
        for k in range(i, j):
            dp(i)(j) = min(dp(i)(j), dp(i)(k) + dp(k+1)(j) +
                           mat(i)(0)*mat(k)(1)*mat(j)(1))
        i += 1
        j += 1

print(dp(0)(N-1))