Java - [프로그래머스]12942 - 최적의 행렬 곱셈

출처

https://school.programmers.co.kr/learn/courses/30/lessons/12942

프로그래머스

 

문제

이 문제는 DP를 이용하여 모든 행렬을 곱하기 위한 최소 곱셈 연산의 수를 구하는 문제이다.

 

풀이

이 문제는 DP를 이용하여 해결하는 문제이다. 연쇄행렬 최소곱셈 알고리즘 (Matrix chain multiplication)이라고 부르는 알고리즘을 사용하였다.

아래 블로그를 참고하여 문제를 해결하였다.

https://source-sc.tistory.com/24

[1][연쇄행렬 최소곱셈 알고리즘] (Matrix chain multiplication)

 

이 문제의 제한사항을 보면, 계산할 수 없는 행렬은 입력으로 주어지지 않는다고 되어있다. 따라서 여러개의 행렬에 대해 결합법칙이 성립하지 않을 경우는 없다.

또 하나 참고해야할 점은, 행렬의 곱셈에 있어 교환법칙은 성립하지 않는다는 점이다. 이 말은, 행렬의 순서는 바꿀 수 없다는 뜻이다.

아래의 점화식을 세워 해결할 수 있다.

• DP[s][e] = s인덱스 부터 e 인덱스까지의 행렬곱에서 곱셈 연산의 최소 횟수
• s와 e 구간을 두 덩어리로 나눈 모든 경우의 수를 고려하여 결정한다.
• DP[s][e] = 왼쪽 행렬 최소 곱셈횟수 + 오른쪽 행렬 최소 곱셈 횟수 + 왼쪽과 오른쪽 결과 행렬을 곱할때의 횟수
• DP[s][e] = MIN(DP[s][m] + DP[m+1][e] + matrix[s][0] * matrix[m][0] * matrix[e-1][1]) (단, s <= m < e) 

코드

class pgs12942 {
    int[][] matrix, dp;

    public int solution(int[][] matrix_sizes) {
        this.matrix = matrix_sizes;
        this.dp = new int[matrix.length + 1][matrix.length + 1];
        return find(0, matrix.length);
    }

    private int find(int s, int e) {
        if (dp[s][e] == 0)
            dp[s][e] = solve(s, e);
        return dp[s][e];
    }

    private int solve(int s, int e) {
        if (e - s == 1) return 0;

        int result = Integer.MAX_VALUE;
        for (int m = s + 1; m < e; m++) {
            int left = find(s, m);
            int right = find(m, e);
            int now = matrix[s][0] * matrix[m][0] * matrix[e-1][1];
            result = Math.min(result, now + left + right);
        }
        return result;
    }

}