[백준] 11049: 행렬 곱셈 순서 - JAVA

03 Aug 2023 in Algorithm on 다이나믹 프로그래밍

https://www.acmicpc.net/problem/11049

풀이

행렬이 여러개 주어지고 어떤 순서로 곱을 했을 때 연산이 최소가 되는지 구하는 문제이다.

AxB인 행렬과 BxC인 행렬을 곱할 때 필요한 연산의 횟수는 AxBxC이다.

행렬 A, B, C가 있을 때 각각 0, 1, 2의 번호라고 하면

dp[1][2]는 BxC의 횟수, dp[0][2]는 AxBxC의 횟수를 저장했다.

---

메모리: 17736KB

시간: 256ms

언어: Java 11

코드

import java.io.*;
import java.util.*;

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[][] matrix = new int[N][2];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            matrix[i][0] = Integer.parseInt(st.nextToken());
            matrix[i][1] = Integer.parseInt(st.nextToken());
        }

        int[][] dp = new int[N][N];

        for (int i = 0; i < N - 1; i++) {
            dp[i][i + 1] = matrix[i][0] * matrix[i][1] * matrix[i + 1][1];
        }

        for (int i = 2; i < N; i++) {
            for (int j = 0; j + i < N; j++) {
                dp[j][i + j] = Integer.MAX_VALUE;

                for (int k = j; k < i + j; k++) {
                    dp[j][i + j] = Math.min(dp[j][i + j],
                            dp[j][k] + dp[k + 1][i + j] + matrix[j][0] * matrix[k][1] * matrix[i + j][1]);
                }
            }
        }

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

    }

}