Problem Solving
boj 11049 : 행렬 곱셈 순서
1ssrek
2016. 9. 9. 23:20
boj 11049 : 행렬 곱셈 순서
https://www.acmicpc.net/problem/11049
divide&conquer와 메모이제이션을 이용하여 해결하였다.
a[i][1] : i번째 행렬의 row, a[i][2] : j번째 행렬의 col.
위와같이 두면,
1. f(i,j) : i번째 행렬에서 j번째 행렬까지의 최소 곱셈 수
2. f(i,j) = min { f(i,i) + f(i + 1,j) + a[i][1]*a[i+1][1]*a[j][2] , f(i,i+1) + f(i+2,j) + a[i][1]*a[i+2][1] + a[i][1]*a[i+2][1]*a[j][2], ... , f(i,j-1) + f(j,j) + a[i][1]*a[j][1]*a[j][2] }
중복된 연산을 제거하기 위해 f(i,j)를 메모이제이션한다.