[백준 - 11049] 행렬 곱셈 순서

행렬의 순서는 바꿀 수 없지만, 괄호를 치는 위치는 바꿀 수 있다. 결국 i번부터 j번 행렬을 곱하는 최소 비용을 저장하는 구간 DP 문제다.

dp[length][start]에 길이가 length인 연속 행렬 묶음의 최소 연산 횟수를 두고, 중간 분할점 k를 모두 확인했다.

cost(i, j) = min(
  cost(i, k) + cost(k + 1, j)
  + row(i) * col(k) * col(j)
)

길이 2인 구간부터 시작해 긴 구간으로 확장하면, 필요한 작은 문제의 답이 이미 계산돼 있다. 행렬의 실제 값을 곱하는 문제가 아니라 곱셈 순서의 비용만 누적하는 문제로 바꿔 보는 것이 핵심이었다.

문제: 11049 행렬 곱셈 순서 · 코드: GitHub에서 보기