백준 11049 행렬곱셈순서

행렬곱셈순서(백준 11049)

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

점화식을 세우지 못해, 아이디어를 확인하였으나
결국 개념이 이해되지 않아 고민하였던 문제이다
i부터 j까지의 순회하며,
k를 통해 결합의 위치를 나누어 주는 방식이다
그러한 점화식으로
dp[i][j] = min(dp[i][k] + di[k+1][j] + di * dk * dj)를 통해
i와 j 행렬을 곱할 때, 그 사이에 다른 행렬 k가 들어가게 되는 경우,
i부터 k까지와 k+1부터 j까지의 부분 문제로 나누어 해결할 수 있음
따라서 가능한 k 부분의 최소 곱셈 횟수를 구하여 문제를 해결할 수 있음

Code

import sys
import math

# 연쇄 행렬 곱셈
# dp[i][j] : i번째 행렬부터 j번째 행렬까지 곱했을 때의 최소 곱셈 연산 횟수
# dp[i][i] = 0 : 행렬이 하나이기에 곱셈이 일어나지 않음

# k가 1부터 j-1 까지 순회하면서 결합의 위치를 나누어주는 변수
# di * dk * dj -> 곱셈 연산 횟수 (di x dk, dk x dj 배열)
# dp[1][4] = dp[1][k] + dp[k+1][4] + d1 * dk * d4
# dp[1][4] : 1번째 행렬부터 4번쨰 행렬까지 곱했을 때의 최소 곱셈 연산 횟수
# dp[1][k] + dp[k+1][4] 는 dp[1][1] + dp[2][4], dp[1][2] + dp[3][4], dp[1][3] + dp[4][4]의
# 결과 중 최솟값이 들어있음
# 최종적인 점화식은
# dp[i][j] = min(dp[i][k] + dp[k+1][j] + d(i-1) * dk * dj) (다만 i <= k <= j-1)


inp = sys.stdin.readline

num = int(inp().strip())

origin = []

for i in range(num):
    r,c = map(int,inp().split())
    origin.append((r,c))

dp = [[math.inf for _ in range(num)] for _ in range(num)]

for i in range(num):
    dp[i][i] = 0

for i in range(1,num):
    for j in range(num - i):
        for k in range(j,j+i):
            dp[j][j+i] = min(dp[j][j+i],
                             dp[j][k] + dp[k+1][j+i] + origin[j][0] * origin[k][1] * origin[j+i][1])

print(dp[0][num-1])

해결 아이디어

1. dp를 초기화 (inf) 후,
   자기자신인 경우는 행렬 곱셉 횟수가 0 이므로 초기화
   
2. dp[i][i] 근처에 있는 값부터 채워나간다.
   ex : 1~2,2~3,3~4… 이런식으로 근처에 있는 행렬의 곱셈을 더해나간다
   
3. 기존의 값이 더 크다면 내버려 두되,
   그렇지 않다면, 좌측과 상단의 값 그리고 행렬의 곱셈을 통해 해당 칸을 채운다
   =>1~3,3~5 이런 방식의 행렬 곱셈 횟수를 채워나간다
   ex : dp[1][3] : 1부터 3까지의 행렬 최소 곱셈 횟수
   
4. 3을 반복한 후, dp[0][num-1]을 출력
   (dp[0][num-1] : 첫번째 행렬부터, 마지막 행렬까지의 최소 ‘행렬곱셉횟수’)