[백준 / 골드3] 11049 행렬 곱셈 순서 (Java)

문제 보기

사용한 것

• 행렬을 연속해서 곱할 때 최소 연산 횟수를 구하기 위한 Matrix Chain Multiplication 알고리즘

풀이 방법

• DP로 문제를 접근한다.
  • N개의 행렬이 존재하면, M[i, j]를 i 번째 행렬 ~ j 번째 행렬까지 곱한 최소 연산 횟수라고 가정하자.
  • 또한 d[0] ~ d[N]을 d[i-1]은 i 번째 행렬의 행의 수, d[i]는 i 번째 행렬의 열의 수라 하자.
  • M[1,3]은 (A x B) x C or A x (B x C) 중 연산 횟수가 더 작은 값일 것이다.
  • 이 것은 M[1,1] + M[2,3] x d[0] x d[1] x d[3]과 M[1,2] + M[3,3] x d[0] x d[2] x d[3] 중에 작은 값인 것과 같다.
  • 이렇게 점차적으로 연산하는 것을 반복하면 M[1,N]을 구할 수 있고, 이 것이 1 번째 행렬 ~ N 번째 행렬까지 곱한 최소 연산 횟수와 같다.
• 위에 설명한 Matrix Chain Multiplication으로 문제를 풀이한다.

코드

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int d[] = new int[N + 1];
        for (int i = 0; i < N; i++) {
            String[] split = br.readLine().split(" ");
            d[i] = Integer.parseInt(split[0]);
            d[i + 1] = Integer.parseInt(split[1]);
        }

        long[][] dp = new long[N + 1][N + 1];
        for (int idx = 1; idx < N; idx++) {
            for (int i = 1; i <= N - idx; i++) {
                int j = i + idx;
                dp[i][j] = Long.MAX_VALUE;
                for (int k = i; k < j; k++) {
                    dp[i][j] = Math.min(dp[i][k] + dp[k + 1][j] + d[i - 1] * d[k] * d[j], dp[i][j]);
                }
            }
        }

        System.out.println(dp[1][N]);
    }
}