백준 11049 행렬의 곱셈 순서

문제

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

11049번: 행렬 곱셈 순서

---

DP로 접근해서 해결한 문제입니다. 점화식이 쉽게 생각나지 않아서 도움을 많이 받았습니다. 이 문제는 주어진 행렬의 곱셈 순서에 따라 연산 횟수가 달라지는데 그중 최소 연산 횟수를 찾는 문제입니다. 과정은 다음과 같습니다.

• 값을 저장할 dp 리스트를 이차원으로 만듭니다 dp [i][j] = i행렬부터 j행렬까지의 최소 연산
• 행렬 간의 곱을 여러 경우로 만들어 낼 수 있어서 시작 행렬부터 마지막 행렬에 도달 하기까지 일정 거리를 늘려 나가며 곱셈을 진행합니다. 중간에 구분 자를 두어서  구간을 나누어 분할 정복 형식으로 계산합니다.
• 점화식의 마지막 부분에 현재 구간 행렬 곱셈 연산수를 곱해서 더해 줍니다.

---

소스코드 

import sys

input = sys.stdin.readline

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

for gap in range(1, N):  # 행렬사이의 거리
    for start in range(N-gap):  # 시작점 시작점에서 gap을 더했을때 N보다 작아야함
        end = start+gap
        dp[start][end] = sys.maxsize
        for mid in range(start, end):  # 중간 구분 값
            dp[start][end] = min(dp[start][end],
                                 dp[start][mid]+dp[mid+1][end]+arr[start][0]*arr[mid][1]*arr[end][1])
print(dp[0][N - 1])