최적의 행렬 곱셈

문제출처: https://programmers.co.kr/learn/courses/30/lessons/12942

문제설명

크기가 a by b인 행렬과 크기가 b by c 인 행렬이 있을 때, 두 행렬을 곱하기 위해서는 총 a x b x c 번 곱셈해야합니다.
예를 들어서 크기가 5 by 3인 행렬과 크기가 3 by 2인 행렬을 곱할때는 총 5 x 3 x 2 = 30번의 곱하기 연산을 해야 합니다.

행렬이 2개일 때는 연산 횟수가 일정 하지만, 행렬의 개수가 3개 이상일 때는 연산의 순서에 따라서 곱하기 연산의 횟수가 바뀔 수 있습니다. 예를 들어서 크기가 5 by 3인 행렬 A, 크기가 3 by 10인 행렬 B, 크기가 10 by 6인 행렬 C가 있을 때, 순서대로 A와 B를 먼저 곱하고, 그 결과에 C를 곱하면 A와 B행렬을 곱할 때 150번을, AB 에 C를 곱할 때 300번을 연산을 해서 총 450번의 곱하기 연산을 합니다. 하지만, B와 C를 먼저 곱한 다음 A 와 BC를 곱하면 180 + 90 = 270번 만에 연산이 끝납니다.

각 행렬의 크기 matrix_sizes 가 매개변수로 주어 질 때, 모든 행렬을 곱하기 위한 최소 곱셈 연산의 수를 return하는 solution 함수를 완성해 주세요.

class Solution {
    int[][] mat;
    int[][] dp;
    
    public int solution(int[][] matrix_sizes) {
        int answer = 0;
        mat = matrix_sizes;
        dp = new int[mat.length][mat.length];
        return helper(0, matrix_sizes.length - 1);
    }
    
    public int helper(int x, int y) {
        if (x == y) {
            return 0;
        }
        if (dp[x][y] != 0) return dp[x][y];
        int min = Integer.MAX_VALUE;
        for (int i = x; i < y; i++) {
            min = Math.min(min, helper(x, i) + helper(i + 1, y) + mat[x][0] * mat[i][1] * mat[y][1]);
        }
        dp[x][y] = min;
        return min;
    }
}

helper 메소드는 매트릭스의 x ~ y 범위 안에서 최소값을 반환한다. 계산한 최소값은 dp[x][y]에 저장해주고 이미 계산된 최소값이 있는지 확인함으로써 쓸데없는 계산낭비를 방지한다.

for (int i = x; i < y; i++) {
     min = Math.min(min, helper(x, i) + helper(i + 1, y) + mat[x][0] * mat[i][1] * mat[y][1]);
}

이 부분이 이 문제의 핵심 코드이다. (x ... y) 범위 안에 있는 행렬들을 곱했을때 최소값을 구해야하기 때문에 (x ... i) 범위안에 있는 행렬의 곱셈 최소값과 (i + 1 ... y) 범위 안에 있는 행렬의 곱셈 최소값을 더해준뒤 남은 두 행렬을 곱해서 더해준다. 이때 남은 행렬은 [mat[x][0], mat[i][1]], [mat[i][1], mat[y][1]] 이 되기 때문에, mat[x][0] mat[i][1] mat[y][1] 를 더해주면 된다.