[백준 #11437] 최적의 행렬 곱셈 - JAVA(자바)

문제

https://school.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 함수를 완성해 주세요.

해설

행렬 연산은 순서에 따라 곱셈의 횟수가 달라진다. 모든 가능한 곱셈 순서를 비교해야 최적의 결과를 찾을 수 있는데 단순히 모든 경우를 고려하면 time out이 발생한다. 따라서 이 과정에서 이미 연산한 결과를 기억하는게 필요하고 따라서 Dynamic Programming 기법을 사용해야 한다.

 

예를 들어, A​₁, A₂, A₃, A₄ 를 곱한다고 할 때, ​A₂, A₃의 최적화 결과는 여러 분할 방식에서 반복적으로 사용된다. DP는 이러한 중복 계산을 방지하고, 이전에 계산한 값을 테이블에 저장하여 재사용한다.

코드

import java.util.*;

class Solution {
    
    public static final int INF = Integer.MAX_VALUE;
    
    public int solution(int[][] matrix_sizes) {
        int n = matrix_sizes.length;
        int[][] dp = new int[n][n]; // dp[x][y]: x번째 행렬부터 y번 행렬까지에서 최소 연산 수
        for(int[] row : dp){
            Arrays.fill(row, INF);
        }
        for(int i = 0; i < n; i++){
            dp[i][i] = 0;
        }
        for(int g = 1; g < n; g++){ // gap
            for(int s = 0; s < n; s++){ // 시작 배열 idx
                int e = s+g; // 끝 배열 idx
                if(e >= n) break;
                for(int m = s; m < e; m++){
                    dp[s][e] = Math.min(dp[s][e], dp[s][m] + dp[m+1][e] + (matrix_sizes[s][0] * matrix_sizes[m+1][0] * matrix_sizes[e][1]));
                }
            }
        }
        return dp[0][n-1];
    }
}