[백준 파이썬 11049번 행렬 곱셈 순서] DP란 벽...

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

11049번: 행렬 곱셈 순서

다시 한 번 겸손을 배울 수 있었던 문제

---

핵심은

1. 어떻게 분할정복 문제로 볼 것인가

2. 어떻게 메모이제이션을 활용할 것인가

3. 어떻게 구현할 것인가

 

무려 3개의 난관을 넘어야 풀 수 있는 문제였다.

 

1. 어떻게 분할정복 문제로 볼 것인가?

ABCDE 행렬이 있을 때

A + BCDE, AB + CDE, ABC + DE, ABCD + E 로 분할하여 최소를 찾을 수 있다가 첫 번째

mergeCost = graph[j][0] * graph[k][1] * graph[j + i][1]
tmpCost = min(tmpCost, ans_graph[j][k] + ans_graph[k+1][j + i] + mergeCost)

이것부터 벽이었다...

 

2. 어떻게 메모이제이션을 활용할 것인가?

2차원 배열을 활용하여

Graph[A][A] -> 0

Graph[A][B] -> min(A * B)

Graph[A][C] -> min(A * B * C)

이런 느낌으로 dp를 형성한다

ans_graph[j][j + i] = tmpCost

 

3. 어떻게 구현할 것인가?

행렬의 곱은 붙어 있어야 가능하기 때문에 일반적인 탐색으로는 불가했다

시작과 끝의 거리가 일정하게 움직여야 했기 때문에 대각선으로 탐색을 해야 했다

for i in range(1, N):
    for j in range(0, N-i):

 

그리고 이 모든 것을 구현하기 위해서 변수의 정의가 가장 중요하다고 생각했다

j : 시작 행렬의 인덱스
j + i : 끝 행렬의 인덱스
k : 중간 행렬의 인덱스
k + 1 : 중간 행렬의 앞 인덱스

그러면 이것을 쉽게 해석할 수 있다!
ans_graph[j][k] + ans_graph[k+1][j + i]
= 시작부터 중간까지 값 + 중간부터 끝까지의 합

---

최종적으로 이 모든 것을 합치면 구현할 수 있다!

N = int(input())
graph = []
for _ in range(N):
    r, c = map(int, input().split())
    graph.append((r, c))

ans_graph = [[0 for _ in range(N)] for _ in range(N)]

for i in range(1, N):
    for j in range(0, N-i):
        tmpCost = int(1e9)
        for k in range(j, j + i):
            mergeCost = graph[j][0] * graph[k][1] * graph[j + i][1]
            tmpCost = min(tmpCost, ans_graph[j][k] + ans_graph[k+1][j + i] + mergeCost)
        ans_graph[j][j + i] = tmpCost

print(ans_graph[0][-1])

---

그리고 참고자료에 대한 압도적 감사...!

https://claude-u.tistory.com/271

#220 백준 파이썬 [11049] 행렬 곱셈 순서