백준 11049번 행렬 곱셈 순서

< 백준 11049번 행렬 곱셈 순서 - 마포 코딩박 >

사용한 알고리즘: DP


 N개의 행렬을 곱할 때, 곱셈 순서에 따라 총 연산수가 달라집니다. 가장 작은 총 연산수를 구하는 문제였습니다.

문제풀이는 다음과 같습니다.

(1) (코드 10~11)
 'dp[x][y]: x번째행렬 ~ y번째 행렬 을 곱할 때 최소 연산수' 라고 설정했습니다.

(2) (코드 29~31)
 행렬을 2개만 묶어서 곱해보면서 dp[i][i+1] 을 초기값으로 구했습니다.

(3) (코드 32~39)
 i~i+k 씩 묶어서 최소연산수(dp)를 구했습니다. k=2~N-1 (3개씩, 4개씩, ... , N개씩 묶어봤습니다.)

(4) (코드 13~19)
 i~i+k 묶음의 dp[i][i+k] 를 계산하는 함수를 만들었습니다.
 전체 i~i+k 구간을 두 구간으로 나누는 가능한 모든 경우를 생각합니다.
 즉 {i, (i+1)~(i+k)}, {i~i+1, (i+2)~(i+k)}, ... , {i~(i+k-1), i+k} 의 모든 경우를 봅니다.
 각각의 경우에서 연산수는 " 두 구간의 최소연산수 합 + 두 구간에서 나오는 행렬을 곱하는 연산수 " 입니다.
 두 구간으로 나누는 모든 경우의 연산수 중 가장 작은 값이 dp[i][i+k] 입니다.

(5) (코드 41)
 구하고자하는 답은 1번째 행렬~N번째 행렬 곱의 최소 연산수 = dp[1][N] 입니다.