[백준] 11049. 행렬 곱셈 순서 - 파이썬

[Gold III]

 

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

11049번: 행렬 곱셈 순서

 

풀이

[백준] 10942. 팰린드롬? - 파이썬 [백준] 9252. LCS 2 - 파이썬 [백준] 7579. 앱 - 파이썬

최근 풀었던 위 3개의 DP 문제와 크게 다를 것이 없었던 문제.

근데 DP는 DP인 걸 알아도.. 문제마다 다른 상황에 맞춰서 풀이를 생각해내기 쉽진 않음.

 

그리고 Line 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])