최적의 행렬 곱셈 [자바]

 

🧫 문제 분석

✔️ 출처

최적의 행렬 곱셈 level 3

📖 문제

 

DP로 풀은 문제

행렬의 곱을 복습하자면 

A(3X5) 와 B(5X7)의 크기의 행렬이 있을때 구 행렬을 곱하면

AB = 3X5X7 이된다. 

 

 

행렬 A, B, C... 이렇게 있을 때

ABCD를 만드는 조합은

ABC D

AB CD

A BCD 

 

이렇게 3가지 가 있고

ABCDE는 

 

A BCDE

AB CDE

ABC DE

ABCD E

4가지가 있다

 

여기서 규칙성을 찾을 수 있고 이를 점화식으로 나타낼 수 있다.

시작과 끝을 지정하고, 중간을 지정해서 분할한 후 

최소값을 찾는 것이다.

// A: s,mid까지 곱한 행렬의 행 크기, B: mid+1,e 까지 곱한 행렬의 열 크기
DP[s][e] = min(DP[s][mid] + DP[mid+1][e] + multiply(A,B)); // mid = s ~ e-1 까지

 

최소값을 찾은 후에는 행렬 크기를 갱신해줘야한다. 

그래야 그 다음 행렬 계산에서 문제 없이 사용가능

matrix[s][e][0] = matrix[s][mid][0];
matrix[s][e][1] = matrix[mid + 1][e][1];

 

 

이런 비슷한 문제가 좀 자주 나오는 것 같다. 

모든 구간 분할 조합을 탐색하는 구간 DP문제

 

문제 풀이에서는 r,c로 루프 변수를 선언하고 또 따로 s,e로 구간을 잡아줬는데

의미없고

루프 변수를 r -> s, c -> e 로 사용하는게 더 좋을 거 같다.

---

🔅 문제 풀이

import java.util.Arrays;

class Solution {
    public int solution(int[][] matrix_sizes) {
        int n = matrix_sizes.length;
        
        // 계산된 행렬
        int[][][] matrix = new int[n][n][2];
        int[][] dp = new int[n][n];
        
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        
        // 자기 자신은 0으로 초기화
        for (int i = 0; i < n; i++) {
            matrix[i][i] = matrix_sizes[i];
            dp[i][i] = 0;
        }
        
        for (int r = n-1; r >= 0; r--) {
            for (int c = r + 1; c < n; c++) {
                int s = r, e = c;
                
                // 중간 부분을 나눠서 모든 조합을 구함
                for (int mid = r; mid < c; mid++) {
                    // dp[r][c] = dp[s][e-1] dp[mid+1][e] + [s~e-1, e ~ c] 행렬 곱
                    int newSize = dp[s][mid] + dp[mid + 1][e] + matrix_multiply(matrix[s][mid], matrix[mid + 1][e]);

                    if (dp[r][c] > newSize) {
                        dp[r][c] = newSize;
                        // 계산된 행렬로 갱신
                        matrix[r][c][0] = matrix[s][mid][0];
                        matrix[r][c][1] = matrix[mid + 1][e][1];
                    }
                }
            }
        }
        
        return dp[0][n-1];
    }
    
    private int matrix_multiply(int[] A, int[] B) {
        return A[0] * B[0] * B[1];
    }
}

 

 

🔅 리팩토링

❗ 오답노트 / 필요한 지식

1.