boj 11049 : 행렬 곱셈 순서

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)를 메모이제이션한다.