bj11049 행렬 곱셈 순서

문제

• 백준 URL: 행렬 곱셈 순서
• 난이도 골드 3

풀이

import sys

input = sys.stdin.readline
n = int(input())
if n==1:exit(print(0))

matrices = [list(map(int,input().split())) for _ in range(n)]

dp = [[sys.maxsize] * n for _ in range(n)]
for i in range(n):dp[i][i] = 0

# length는 곱하는 행렬의 개수 (2개부터 N개까지)
for length in range(2, n+1):
    for i in range(n-length+1): # i는 시작 행렬의 인덱스
        j = i + length - 1  # j는 끝 행렬의 인덱스
        
        # k는 i와 j 사이를 나누는 기준점
        # (i...k)와 (k+1...j) 두 그룹으로 나눔
        for k in range(i, j):
            
            # cost = (i~k 최소비용) + (k+1~j 최소비용) + (두 결과 행렬 곱셈비용)
            cost = dp[i][k] + dp[k+1][j] + matrices[i][0] * matrices[k][1] * matrices[j][1]
            dp[i][j] = min(dp[i][j], cost)

# 최종 결과는 0번째부터 n-1번째 행렬까지 곱하는 최소 비용
print(dp[0][n-1])

i번째 행렬부터 j번째 행렬까지 곱하는 데 필요한 최소 곱셈 횟수를 저장하는 'dp' 테이블을 생성하였다. 점화식은 다음과 같다.
dp[i][j] = min(dp[i][k] + dp[k+1][j] + matrices[i][0] * matrices[k][1] * matrices[j][1])
- i부터 j까지의 행렬 그룹을 k를 기준으로 (i...k)와 (k+1...j) 두 개로 나누는 모든 경우를 확인한다.
- 각각의 부분 문제에 대한 최소 비용(dp[i][k], dp[k+1][j])을 가져오고, 두 결과를 합치는 곱셈 비용을 더해서 작은 값을 찾는다.

좀 더 이해를 돕기위해 예제를 통해 자세히 설명해보면,

length = 2인 경우

for k in range(i, j):
    cost = dp[i][k] + dp[k+1][j] + matrices[i][0] * matrices[k][1] * matrices[j][1]

length가 2일 때, 왼쪽 부분은 i==k가 되어 0이므로 바로 갱신이 가능하고, 오른쪽 부분도 k+1==j이므로 0이 되어 바로 갱신이 가능하다. 따라서 행렬과 행렬을 곱하는 비용으로 바로 갱신된다.

length > 2인 경우

예를 들어 length = 3일 때 dp[0][2]를 구하는 상황이라고 치자.

k=0이면,

• 왼쪽은 dp[0][0] 즉 0이다.
• 오른쪽은 dp[1][2]다. 그런데 값의 차이가 1이므로, length = 2일 때 dp[1][1] + dp[2][2] + 행렬 곱 비용 같은 식으로 미리 계산이 되었음을 알 수 있다.
  k=1이면,
• 왼쪽은 dp[0][1] 이것도 dp[0][0] + dp[1][1] + 행렬 곱 비용으로 계산되어 있다.
• 오른쪽은 dp[2][2] 이므로 0이다.

이런 식으로 다이나믹 프로그래밍이 가능하다. 최적의 풀이 방법인진 모르겠지만 일단 이렇게 풀었다. 다른 풀이 코드도 확인해봐야겠다.