[PY] <!> 11049 : 행렬 곱셈 순서

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

그냥 DP인줄 알았는데

행렬 곱 최소 비용 문제는

• 구간 범위
• 쪼개서 비교를 하고
• 최소비용을 계속 갱신

해나가는 것이 핵심이다.

자를 수 있는 한 최대한 범위를 자르고, 작은 해부터 최적의 해를 알아가는 것인데,
해외 검색 키워드로는 Matrix Chain Multiplication 이 있다.

 

아무 곳에서 잘라서, 왼쪽 오른쪽 그룹을 고려하게 되면 그룹이 더 나눠질 수 없는 상황까지 줄인 다음, 거기서부터 값을 채워나가는 형태를 생각하게 된다. 이게 전형적인 Bottom Up방식으로 피티 지는 설명한다.

dp[i][j] = min(
    dp[i][k] + dp[k+1][j] + (i~k 행렬) * (k+1~j 행렬) 곱셈비용
)  for 모든 k in [i, j-1]

범위 i j를 정의하고 자를 구간 k를 갱신해 나가면서 dp 표를 완성해 나가는 방식인데, 이 k는 결국에 한 번 자름으로써 2개의 구역이 만들어 지니 그 2개 구역에서의 곱셈을 진행하는데 있어 필요한 매개체 역할도 수행하게 된다.

그러면 i*k k*j? 뭐 조금 기호는 다를 수 있겠지만, 여기서 발생하는 곱셈 비용까지 고려한다면 비교 하기전 해야할 계산은 다 끝난 셈이다.

 

그래서 해당 아이디어를 가능한 반영한 채로 작성된 코드를 이렇게 정리 할 수 있었다.

import sys
input = sys.stdin.readline

caseCnt = int(input())
caseList = [0]
dp = [[float('inf')] * (caseCnt + 1) for _ in range(caseCnt + 1)]
for i in range(caseCnt):
    matX, matY = map(int, input().split())
    caseList.append([matX, matY])




for i in range(1, caseCnt + 1):
    dp[i][i] = 0

for length in range(2, caseCnt + 1):
    for i in range(1, caseCnt - length + 2):
        j = i + length - 1
        for k in range(i, j):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + caseList[i][0] * caseList[k][1] * caseList[j][1])

print(dp[1][caseCnt])

이거 PyPy3로 해야한다. 씨