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

문제

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

11049번: 행렬 곱셈 순서

코드

import sys
INF=sys.maxsize

n=int(input())

arr=[]

for i in range(n):
    t1, t2=map(int, input().split())
    arr.append((t1,t2))

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

for i in range(1,n):
    for j in range(n-i):
        if i==1:
            dp[j][j+1]=arr[j][0]*arr[j][1]*arr[j+1][1]
            continue
        dp[j][j+i]=INF
        for k in range(j,j+i):
            dp[j][j+i]=min(dp[j][j+i],
                           dp[j][k]+dp[k+1][j+i]+arr[j][0]*arr[k][1]*arr[j+i][1])

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

생각 정리

dp[a][b]의 의미는 a행렬 부터 b행렬까지 행렬 곱의 최솟값이고

점점 거리(i)를 넓혀가면서 

 

ABCDE연속행렬 곱의 최솟값 =

min(ABCDE,

min(A) + min(BCDE) + 합치는 비용(A행 * A열 * E열),

min(AB) + min(CDE) + 합치는 비용(A행 * B열 * E열),

min(ABC) + min(DE) + 합치는 비용(A행 * C열 * E열),

min(ABCD) + min(E) + 합치는 비용(A행 * D열 * E열)

)

 

최솟값을 구해준다.