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

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

문제

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

문제 분석

조건

여러 개의 행렬을 순서대로 곱할 때, 곱셈 순서(괄호를 치는 순서)에 따라 총 곱셈 연산 횟수가 달라진다. 주어진 행렬들의 곱셈에 필요한 최소 연산 횟수를 구하는 문제

풀이방법

DP를 이용하여 문제를 풀었다.

`dp[i][j]`는 i번째 행렬부터 j번째 행렬까지 곱하는 데 필요한 최소 곱셈 연산 횟수를 의미한다. 행렬이 1개(`i == j`)일 경우 곱셈이 필요 없으므로 0으로 초기화 한다.

`i`부터 `j`까지의 행렬 곱은, 중간의 한 지점 `k`를 기준으로 (`i ~ k`)까지의 곱과 (`k+1 ~ j`)까지의 곱, 이 두 결과를 마지막으로 곱하는 것과 같다. 점화식은 아래와 같다.

dp[start][end] = Math.min(dp[start][end], 
		dp[start][mid] + dp[mid + 1][end] + 
        (matrix_sizes[start][0] * matrix_sizes[mid][1] * matrix_sizes[end][1]));

코드

class Solution {
    public int solution(int[][] matrix_sizes) {
        int[][] dp = new int[matrix_sizes.length][matrix_sizes.length];
        for (int i = 0; i < matrix_sizes.length; i++) {
            dp[i][i] = 0;
        }
        for (int size = 1; size <= matrix_sizes.length; size++) {
            for (int start = 0; start < matrix_sizes.length; start++) {
                int end = start + size;
                if (end >= matrix_sizes.length) {
                    continue;
                }
                dp[start][end] = (int) 1e9;
                for (int mid = start; mid < end; mid++) {
                    dp[start][end] = Math.min(dp[start][end], dp[start][mid] + dp[mid + 1][end] + (matrix_sizes[start][0] * matrix_sizes[mid][1] * matrix_sizes[end][1]));
                }
            }
        }
        return dp[0][matrix_sizes.length - 1];
    }
}