최적의 행렬 곱셈

문제 설명

다이나믹 프로그래밍 문제이다.

우선 알아야할 것은 두 행렬 A, B 가 주어지고 각각의 행렬의 행, 열의 수를 Ra, Rb, Ca, Cb 라고 할 때 두 행렬의 곱이 가능하려면 Ca 와 Rb 가 같아야하며, 행렬의 결과 행렬의 크기는 Ra, Cb 가 된다.

문제의 예제로 주어진 예제로 살펴보면

Input : [[5,3],[3,10],[10,6]]

일 때, (5, 3) 행렬을 A (3, 10) 행렬을 B라고 했을 때 두 행렬의 곱은 (5, 10) 이 된다.

두 행렬을 곱했을 때 필요한 연산 수는 Ra x Ca(Rb) x Cb 가 된다.

접근 방법

다이나믹 프로그래밍으로 접근한다. DP[i, j] 를 주어진 행렬 리스트의 i번째부터 j번째까지의 행렬곱 결과를 최소 연산으로 수행했을 때의 결과라고 가정하자. 전체 구간 [0, T]가 있고, 그 사이의 값 i 가 있다고 가정할 때

DP[0][t] = min(DP[0][t], DP[0][i] + DP[i][T] + R0 x Ri x Ci for i in range(0, T)) 가 된다.

위 수식에서 우측 비교값은, i를 기준으로 i를 포함하는 좌측의 행렬들을 모두 곱했을 때의 최소 연산값 Dp[0][i] i+1 부터 T까지의 행렬들을 모두 곱했을 때의 최소 연산값 Dp[i+1][T] 그리고 좌측 행렬들을 곱해서 나온 행렬과, 우측 행렬들을 모두 곱해서 나온 행렬을 서로 곱했을 때 필요한 연산량을 더한 결과이다.

Source code

import java.util.*;

class Solution {
   int INF = Integer.MAX_VALUE;
   int answer = 0;
   int[][] cache;
   
   int dfs(int left, int right, int [][] matrixSizes) {
       if(left == right) {
           return 0;
       }
       
       if(cache[left][right] != -1) {
           return cache[left][right];
       }
       
       cache[left][right] = 0x01<<30;
       
       for(int i = left ; i < right ; i++) {
           cache[left][right] = Math.min(
               cache[left][right],
               dfs(left, i, matrixSizes) + dfs(i+1, right, matrixSizes) + matrixSizes[left][0] * matrixSizes[i][1] * matrixSizes[right][1]
           );
       }
       
       return cache[left][right];
   }
   
   public int solution(int[][] matrixSizes) {
       this.cache = new int[matrixSizes.length][matrixSizes.length];
       
       for(int i = 0 ; i < cache.length ; i ++) {
           for(int j = 0  ; j < cache.length ; j++) {
               cache[i][j] = -1;
           }
       }
       
       answer = dfs(0, matrixSizes.length - 1, matrixSizes);
       
       return answer;
   }
}