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

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

import sys
input = sys.stdin.readline

if __name__ == '__main__':
    N = int(input())

    nums = list(map(int, input().split()))
    for _ in range(N-1):
        _, c = map(int, input().split())
        nums.append(c)

    # DP
    dp = [[0]*N for _ in range(N)]
    for d in range(N):
        for i in range(N - d):
            j = i + d

            if i == j:
                continue

            dp[i][j] = float('inf')
            for k in range(i, j):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1]
                               [j] + nums[i]*nums[k+1]*nums[j+1])

    print(dp[0][-1])

 

우선, 예제 입력 1의 경우, 5 3 2 6와 같이 데이터를 간략화하여 저장한다.

그 다음, 우리는 DP 중급 난이도쯤 되는 '연쇄행렬곱셈'을 이용하여 이 문제를 풀어낸다.

 

설명을 위한 예시는 아래의 케이스이다.

4
1 7
7 2
2 5
5 6

# 1 7 2 5 6

DP[i][j]는 i~j까지의 최소곱을 뜻한다. 즉, 우리는 DP[0][3]이 필요하다.

여기서 빈칸을 채워나가보자. DP[0][1]은, (1, 7), (7, 2)의 최소곱을 말한다. 즉, 1*7*2 = 14이다. 이런 식으로 대각선 방향으로 진행하면 다음과 같이 된다.

다음으로, DP[0][2]의 값을 정해보자. 우리는 DP[0][1] = 14라는 정보를 이용한다.

(1, 7), (7, 2)을 곱하면 (1, 2)가 되며, 그 다음에는 (1, 2) * (2, 5)을 하여 최종적으로 DP[0][2]에 해당하는 연산을 수행하게 된다. 여기서 DP[0][2] = DP[0][1] + nums[0]*nums[2]*nums[3] = 14 + 1*2*5 = 24가 성립된다.(아직까진 일반적인 경우는 아니다.)

 

마지막으로 DP[0][3]이다. 이 값을 구하기 전에 경우를 나눠보자.

 - DP[0][0] + DP[1][3]

 - DP[0][1] + DP[2][3]

 - DP[0][2] + DP[3][3]

첫번째 경우를 보자. 저장되어있는 DP[0][0] + DP[1][3]을 더한 뒤, 이 두 행렬을 곱할 때 발생하는 곱셈의 개수를 더해주면 원하는 값이 나온다. 이 곱셈은 (1, 7)*(7, 6)과 같다. 즉, 1*7*6을 더해주면 된다는 것이다.

이런 식의 계산을 모든 케이스에 대해서 해주고, 거기서 최소값을 얻으면 된다. 이제야 일반화가 된다. 점화식은 아래와 같다.

DP[i][j] = min(DP[i][j], DP[i][k] + DP[k+1][j] + nums[i]*nums[k+1]*nums[j+1] (i≤k<j)

 

이렇게 DP는 완성된다.