[BOJ] 11049번 : 행렬 곱셈 순서(DP)

목차

접근

DP를 이용해서 행렬 곱셈을 진행할 때 최소가 되는 곱셈 연산의 횟수를 구하는 문제다.

행렬 자체는 연산이 가능하도록 순서대로 주어지는데, 우리는 연산 순서의 우선순위를 결정해야한다.

예시에도 잘 나와있지만, 일단 옮겨보도록 하겠다.

 

예를 들어, A의 크기가 5×3이고, B의 크기가 3×2, C의 크기가 2×6인 경우에 행렬의 곱 ABC를 구하는 경우를 생각해보자.

• AB를 먼저 곱하고 C를 곱하는 경우 (AB)C에 필요한 곱셈 연산의 수는 5×3×2 + 5×2×6 = 30 + 60 = 90번이다.
• BC를 먼저 곱하고 A를 곱하는 경우 A(BC)에 필요한 곱셈 연산의 수는 3×2×6 + 5×3×6 = 36 + 90 = 126번이다.

이렇게 행렬은 연산 우선순위를 변경함으로써, 같은 연산을 진행할 때에도 연산의 횟수가 달라짐으로 연산 횟수를 줄일 수 있다.

 

그럼 우리는 어떻게 이 우선순위를 결정지을 수 있을까?

 

먼저 쉽게 구할 수 있는 부분부터 생각해보자.

행렬 A(5 x 3), B(3 x 2)가 있다면, 행렬 곱셈 `AB`를 구하기 위한 곱셈 연산의 최소 횟수는 몇회일까?

당연히 뭐 할 것도 없이, `5 * 3 * 2 = 30`가 될 것이다.

그니까 거리 하나짜리 행렬곱(연속된 행렬의 곱)은 곱셈 연산의 최소 횟수를 구할 수 있다는 것이다. 

 

그럼 이제 다음으로 넘어가보자.

행렬 A(5 x 3), B(3 x 2), C(2 x 6)가 있을 때, 행렬 곱셈 `ABC`를 구하기 위한 곱셈 연산의 최소 횟수를 생각해보자. 최소 횟수를 생각하기 이전에 나눠질 수 있는 형태를 먼저 고민해보자.

`ABC`는 `(AB)C`, `A(BC)` 이렇게 두가지로 행렬 곱셈에 대한 우선순위가 나눠질 수 있다.

그럼 연속된 행렬의 곱의 곱셈 연산의 최소 횟수를 먼저 구해보자.

`AB = 5 * 3 * 2 = 30`, `BC = 3 * 2 * 6 = 36`

그리고 각각의 전체 횟수를 구해보자.

`(AB)C = 30 + 5(A의 행) * 2(C의 행) * 6(C의 열) = 90`

`A(BC) = 36 + 5(A의 행) * 3(A의 열) * 6(C의 열) = 126`

 

그럼 `ABC`의 곱셈 연산의 최소 횟수는 90회가 된다는 것을 알 수 있다.

위의 과정을 보면, 행렬을 쪼개서 곱셈 연산의 최소 횟수를 구해나가는 과정임을 알 수 있다.

 

이 과정을 dp에 저장해나가는 방식으로 생각해보자.

dp의 차원은 `(n, n)`으로 구성하고, 그 의미가 dp[i][j] 는 행렬 곱이 `A_0A_1A_2A_3...A_n` 이렇게 주어질 때 `A_i` 부터 `A_j`까지의 곱셈 연산의 최소 횟수를 저장하는 것으로 받아들이자.

 

그럼 위의 과정을 수식으로 표현해보겠다.

$min(ABC) = min( \\ dp[A][C], \\ dp[A][A] + dp[B][C] + A[0] * A[1] * C[1], \\ dp[A][B] + dp[C][C] + A[0] * B[1] * C[1]\\)$

 

`dp[A][A]` 같이 대각에 위치한 자기 자신과의 값은 0일 것이고, `dp[B][C], dp[A][B]`와 같이 거리가 1인 행렬(연속된 행렬)은 곱셈 연산의 최소 횟수를 위에서 언급했듯 그냥 구하면 된다.

 

이 과정을 일반화시켜서 점화식처럼 생각할 수 있다.

$min(A_0A_1A_2...A_n) = min( \\ dp[0][n], \\ dp[0][0] + dp[0][n-1] + A_0[0] * A_0[1] * A_n[1], \\ dp[0][1] + dp[2][n-1] + A_0[0] * A_1[1] * A_n[1] \\ ... \\ dp[0][n-2] + dp[n-1][n-1] + A_0[0] * A_{n-1}[1] * A_n[1])$

 

이렇게 작은 거리부터 Bottom-UP 방식으로 DP 테이블을 할당해나가면, 결국 마지막까지 구해나갈 수 있다.

해결

접근에서 말한 것처럼, 2차원 배열을 이용한 DP로 문제를 해결할 수 있다.

점화식에 대한 아주 큰 힌트를 얻은 레퍼런스는 아래와 같다.

Ref:

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

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

 

코드

import sys

input = sys.stdin.readline

N = int(input())
matrix = [list(map(int, input().split())) for _ in range(N)]
dp = [[0] * N for _ in range(N)]

for term in range(1, N):
    for i in range(N-term):
        j = i + term
        
        if term == 1:
            dp[i][j] = matrix[i][0] * matrix[j][0] * matrix[j][1]
            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] + matrix[i][0] * matrix[k][1] * matrix[j][1])
            
print(dp[0][N-1])