[백준 11049번] 행렬 곱셈 순서 (Python3)

import sys
input = sys.stdin.readline
INF = 10**12

N = int(input())
matrix = []
for i in range(N):
  matrix.append([*map(int,input().split())])

DP = [[INF]*N for i in range(N)]
for i in range(N):
  DP[i][i] = 0

for k in range(1,N):
  for i in range(N-k):    
    for j in range(i,i+k):
      DP[i][i+k] = min(DP[i][i+k],DP[i][j]+DP[j+1][i+k]+matrix[i][0]*matrix[j][1]*matrix[i+k][1])

print(DP[0][N-1])

대략 한달이 넘도록 풀지 못했던 문제.

DP에서 구간의 크기를 변수로 생각해야 한다는걸 떠올리기가 정말 어려웠다.

 

알고리즘을 요약하면,

1. DP[i][j]는 i번째 행렬부터 j번째 행렬까지 곱셈을 했을때의 최솟값을 의미한다.

2. DP[i][i] = 0, 나머지는 INF로 설정한다.

3. 3중 for문을 돌린다. 이때 k는 구간의 크기, i는 시작위치, j는 중심을 의미한다.

4. i~j까지 곱했을 때의 행렬과 j~i+k까지 곱했을 때의 행렬, 두 행렬을 곱할 때의 횟수 + i~j를 곱할때 횟수 + j~i+k를 곱할때 횟수의 최솟값을 구해준다.

5. 0~N-1까지의 행렬을 모두 곱했을 때의 최솟값 (DP[0][N-1]) 을 출력한다.

 

 

오늘의 교훈) DP 응용 문제를 열심히 해야겠다