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

백준 11049

N = int(input())
mat_sizes = [[0, 0]] + [list(map(int, input().split())) for _ in range(N)]

INF = 10**12
# dp[시작 행렬 인덱스][마지막 행렬 인덱스] = 최소 곱셈 횟수
dp = [[0 for _ in range(N+1)] for _ in range(N+1)]

for i in range(1, N): # 구간 설정, 마지막 행렬 인덱스 - 시작 행렬 인덱스
    for j in range(1, N-i+1): # 시작 인덱스, 시작 + 구간 <= 전체 행렬 길이
        dp[j][i+j] = INF
        for k in range(j, i+j): # 구간을 나누는 기준, 플로이드 워셜처럼 생각하면 된다
        	# dp[j 번째 행렬][i+j 번째 행렬]의 곱셈 횟수 최솟값 = 시작 ~ k 번째 + k+1 번째 ~ 마지막 행렬 까지 곱셈 횟수 중 최솟값
            dp[j][i+j] = min(dp[j][i+j],
                             dp[j][k] + dp[k+1][i+j] + mat_sizes[j][0]*mat_sizes[k][1]*mat_sizes[i+j][1])
            
print(dp[1][N])