[BOJ] 11049. 행렬 곱셈 순서

문제 원본 : https://www.acmicpc.net/problem/11049

11049번: 행렬 곱셈 순서

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int[][] mat = new int[n][2];
        int[][] dp = new int[n][n];
        int[][][] mem = new int[n][n][2];

        StringTokenizer st = null;
        for (int i = 0; i < n; ++i) {
            st = new StringTokenizer(br.readLine());
            mat[i][0] = Integer.parseInt(st.nextToken());
            mat[i][1] = Integer.parseInt(st.nextToken());
            mem[i][i][0] = mat[i][0];
            mem[i][i][1] = mat[i][1];
        }

        for (int i = 0; i < n - 1; ++i) {
            dp[i][i + 1] = mat[i][0] * mat[i][1] * mat[i + 1][1];
            mem[i][i + 1][0] = mat[i][0];
            mem[i][i + 1][1] = mat[i + 1][1];
        }

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

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

                mem[j][l][0] = mat[j][0];
                mem[j][l][1] = mat[l][1];
            }
        }

        bw.write(String.valueOf(dp[0][n - 1]));

        bw.close();
        br.close();
    }
}

• 다이내믹 프로그래밍 문제
• 파일 합치기 문제와 비슷한 문제이다.
• 중간에 만들어지는 행렬의 행과 열의 값을 mem 배열에 저장해가면서 풀었다.