[DP]행렬곱

1번째부터 n번째의 모든 행의 곱인을 구하기 위해서는 여러가지 방법이 있다. 우선 

첫번째 행렬이 pxq인 행렬이고 두번째 행렬이 qxr인 행렬인 경우 결과값으로 나오는 행렬은 pxr인 행렬이라는 것은 고등학교 수학 수업중 배웠을 것이다. 또 간단한 행렬에 대하여 곱을 수행해보면 총 연산 횟수는 pxqxr이라는 것을 알게 될 것이다. 그렇다면 

 이러한 여러 행렬의 곱연산은 어떨까? 

행렬은 일단 교환법칙이 성립되지 않기 때문에 서로 자리를 바꾸게 되면 결과가 바뀌게 된다. 하지만 결합법칙은 성립하여 

 

이 두가지의 결과는 같다. 하지만 결과는 같을지라도 결합의 방식에 따라서 계산 횟수가 달라지게 된다. 예를 들면 행렬 A를 10x100, B는 100x5, C는 5x50이라고 할 때 새 행렬 ABC는 10x50의 형태일 것이다. 결합법칙은 성립하므로 먼저 AB를 곱하고 C를 곱하는 (AB)C의 연산횟수는 (10x100x5)+(10x5x50)=7500이다. 또 다른 방법인 A(BC)는 (100x5x50)+(10x100x50)= 75000의 연산 횟수가 필요하다. 이렇듯 같은 행렬곱이라도 어떠한 방법으로 곱을 해나가는지에 따라 연산횟수의 차이가 달라지기 때문에 최적화의 차원에서 이는 중요한 문제이다. 이제부터 알아갈 것은 행렬곱의 최적 순서를 알아가는 방법이다.

행렬곱을 일반화하기 위해 i번째 행렬부터 j부터 행렬의 곱을 구한다고 가정하자.

이 때 는 의 행렬이다.

 최적의 행렬곱을 구하기위해 두개의 sub-행렬로 나누는 지점을 k라 하고 이때 나누어진 두 행렬곱의 연산횟수는 최적값이라고 하자. 첫번째 행렬곱은 i~k까지, 두번째 행렬곱을 k+1~j라고 할 때 각각 최소 연산횟수를 

,

라 하자. 그렇다면 

= + +일 것이다. 끝부분의 P수열의 곱은 두 sub-행렬의 곱의 연산 횟수이다. 그렇다면 이제 남은 것은 모든 가능한 k로 만들어지는 여러 계산 조합 중 가장 작은 값을 고르면 된다.

package dynamicProgramming; import java.io.BufferedReader; import java.io.FileInputStream; import java.io.IOException; import java.io.InputStreamReader; /** * Created by junhyeok on 2017-07-15. * Problem No: 11049 */ public class MatrixMultiply { public static int[] p; public static void main(String[] args) throws IOException { //BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("matrixMultiply.txt"))); int n = Integer.parseInt(br.readLine()); p = new int[n + 1]; for (int i = 0; i < n; i++) { String[] params = br.readLine().split(" "); p[i] = Integer.parseInt(params[0]); if (i == n - 1) p[i + 1] = Integer.parseInt(params[1]); } System.out.println(cal(n)); } public static int cal(int n) { int[][] m = new int[n + 1][n + 1]; // i==j는 0으로 초기화 . i<=j인 부분은 사용하지 않는다 for (int r = 1; r <= n - 1; r++) { // 대각선 인덱스. i==j인 대각선을 제외한 1~n-1 까지의 대각선이다. for (int i = 1; i <= n - r; i++) { // row 인덱스. 1부터 n-r까지 반복. 이는 대각선 상의 모든 i 인덱스이다. int j = i + r; //대각선 상의 col 인덱스. if (i == j) m[i][j] = 0; else { m[i][j] = Integer.MAX_VALUE; for (int k = i; k <= j - 1; k++) { if (m[i][j] > m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]) m[i][j] = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]; } } } } return m[1][n]; } }