[Programmers] 최적의 행렬 곱셈 (Java)

1.  문제 링크

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

2.  문제

크기가 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 함수를 완성해 주세요.

3.  제한사항

• 행렬의 개수는 3이상 200이하의 자연수입니다.
• 각 행렬의 행과 열의 크기는 200이하의 자연수 입니다.
• 계산을 할 수 없는 행렬은 입력으로 주어지지 않습니다.

입출력 예

4.  소스코드

import java.util.Arrays;

class Solution {
    public int solution(int[][] matrix_sizes) {
    	// dp[x][y] = x번째 행렬부터 y번째 행렬까지의 곱을 위해 필요한 최소 곱셈 연산 수
        int[][] dp = new int[matrix_sizes.length][matrix_sizes.length];
        init(dp, matrix_sizes); // dp 배열 초기화
        return getOptimalMultiplicationNum(dp, matrix_sizes);
    }

	// 필요한 최소 곱셈 연산 수 계산 메서드
    public int getOptimalMultiplicationNum(int[][] dp, int[][] matrix_sizes) {
    	// 행렬의 곱은 행과 열의 길이가 맞아야 곱을 진행할 수 있기 때문에
        // 행렬의 곱셈 순서를 임의로 설정할 수 없고 순차적으로 진행해야 한다
    	// 그렇다면 x번째 행렬부터 y번째 행렬까지 필요한 최소 곱셈 연산 수를 구할 때, 중간에 어떠한 행렬을 기준으로
        // x번째 행렬부터 z번째 행렬까지, z + 1 번째 행렬부터 y번째 행렬까지 각각의 최소 곰셈 연산 수를 구한 다음 그 둘을 더하고
        // x번째 행렬부터 z번째 행렬까지 곱했을 때의 결과값과 z + 1번째 행렬부터 y번째 행렬까지 곱했을 때의 결과값을 곱할 때 필요한 곱셈 연산 수를 더하면
        // x번째 행렬부터 y번째 행렬까지 필요한 곱셈 연산 수를 구할 수 있다
        // 그러므로 이를 활용하여 아래와 같은 점화식을 만든다
        // dp[x][y] = min(dp[x][y], dp[x][z] + dp[z + 1][y] + (x부터 z까지 곱한 행렬과 z + 1부터 y까지 곱한 행렬 사이의 곱셈 연산 수)
        // 	- 위 점화식을 시작 행렬부터 3개의 행렬을 곱하는 경우, 4개의 행렬을 곱하는 경우, ... 이렇게 순차적으로 적용하면서 dp 배열을 채워나가며 최소 곱셈 연산 수를 구한다
        for(int length = 2; length < matrix_sizes.length; length++) {
            for(int startIdx = 0; startIdx + length < matrix_sizes.length; startIdx++) {
                int endIdx = startIdx + length;
                for(int middleIdx = startIdx; middleIdx < endIdx; middleIdx++) {
                    int multiplicationNum = dp[startIdx][middleIdx] + dp[middleIdx + 1][endIdx] +
                            (matrix_sizes[startIdx][0] * matrix_sizes[middleIdx][1] * matrix_sizes[endIdx][1]);
                    dp[startIdx][endIdx] = Math.min(dp[startIdx][endIdx], multiplicationNum);
                }
            }
        }

        return dp[0][matrix_sizes.length - 1];
    }

    public void init(int[][] dp, int[][] matrix_sizes) {
    	// 최솟값을 구하기 위해 dp 배열을 최댓값으로 초기화한다
        // idx번째 행렬과 idx + 1번째 행렬을 곱할 때 필요한 곱셈 연산 수는 먼저 구한다
        for(int idx = 0; idx < matrix_sizes.length - 1; idx++) {
            Arrays.fill(dp[idx], Integer.MAX_VALUE);
            dp[idx][idx] = 0;
            dp[idx][idx + 1] = matrix_sizes[idx][0] * matrix_sizes[idx][1] * matrix_sizes[idx + 1][1];
        }
    }
}