[백준] 11049번 : 행렬곱셈순서

11049번: 행렬 곱셈 순서

해당문제는 다이나믹 프로그래밍 문제로 행렬 곱을 연산할때 순서가 뒤바뀌면 행렬 곱셈량이 달라진다.

행렬 곱셈량의 최소값을 구하기위해서는 아래와 같이 문제를 정의하고 해결하였습니다.

행렬 A,B,C,D가 있다고 할때

1. A인 자기자신은 곱셈을 할수 없으므로 0으로 초기화 한다.
2. 길이가 2인 경우는 (AB), (BC) 각각 곱한 결과 값을 갖는다.
3. 길이가 3인 경우는 (AB),C, A(B,C) 중 최소 값이다.
4. 길이가 4인 경우는 A(BCD), (AB)(CD), (ABC)(D) 중 최소 값이다.

위의 내용을 점화식으로 정리한뒤 코드로 정리하면 아래와 같다.

dp[n][m]은 n번째 행렬부터 m번째 행렬을 곱을 연산시 곰셈량의 최소값을 저장하는 배열이다.

dp[n][m]은 min(d[n][k] + d[k+1][m]) 이다.즉, A(BCD), (AB)(CD), (ABC)(D) 중 최소 값을 찾는 과정이다.

import sys
input = sys.stdin.readline

N = int(input())
dp = [[[0, 0, 0] for _ in range(N)] for _ in range(N)]
for i in range(N):
    r, c = map(int, input().split())
    dp[i][i] = [r, c, 0]

for i in range(N-1):
    temp = dp[i][i][0] * dp[i+1][i+1][0] * dp[i+1][i+1][1]
    dp[i][i+1] = [dp[i][i][0], dp[i+1][i+1][1], temp]

for i in range(2, N):
    for j in range(N-i):
        mincost = int(2**31)
        for k in range(i):
            r1, c1, cost1 = dp[j][j+k][0], dp[j][j+k][1], dp[j][j+k][2]
            r2, c2, cost2 = dp[j+k+1][i+j][0], dp[j+k+1][i+j][1], dp[j+k+1][i+j][2]

            temp = cost1 + cost2 + (r1 * c1 * c2)
            if mincost > temp:
                mincost = temp
                n_r1 = r1
                n_c1 = c2

        dp[j][j+i] = [n_r1, n_c1, mincost]

print(dp[0][N-1][2])