P.11049 행렬 곱셈 순서

코드

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

public class Main {

    static Matrix[] matrices;

    static public class Matrix {
        int r, c;

        public Matrix(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }

    static int[][] dp;

    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());
        matrices = new Matrix[n];
        for (int i = 0; i < n; i++) {
            int[] line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

            matrices[i] = new Matrix(line[0], line[1]);
        }
        dp = new int[n][n];
        for (int i = 0; i < n; i++) Arrays.fill(dp[i], Integer.MAX_VALUE);

        bw.write(Integer.toString(solve(0, n - 1)));
        bw.flush();
    }

    private static int solve(int start, int end) {
        if (start == end) return dp[start][end] = 0;
        if (dp[start][end] != Integer.MAX_VALUE) return dp[start][end];

        for (int i = start; i < end; i++) {
            int ans = solve(start, i) + solve(i + 1, end) + (matrices[start].r * matrices[i].c * matrices[end].c);
            dp[start][end] = Math.min(dp[start][end], ans);
        }

        return dp[start][end];
    }
}

코드 설명

n번째 행렬 ~ m번째 행렬까지의 곱을 구하는 것이 문제의 핵심 포인트다.

따라서 dp 배열을 다음과 같이 생각할 수 있다.

dp[n][m] = n번째 ~ m번째 행렬까지의 곱의 최솟값

 

간단하게 하기 위해 n번째 ~ m번째 행렬의 곱을 [n][m]이라고 하겠다.

이 dp의 문제점은 [n][m]은 [n][i] * [i][m]이라는 하위 문제들로 이루어진 가장 큰 문제라는 것이다.

5 3
3 2
2 6

다음과 같은 예시에서 구해야 할 답은 [1][3] (1번째 행렬 ~ 3번째 행렬의 곱)이다.

그런데 [1][3]은 다음 두 가지 방식으로 구할 수 있다.

1. M(5 x 3) * M(3 x 2) + M(5 x 2) * M(2 x 6) = 5 * 3 * 2 + 5 * 2 * 6
2. M(3 x 2) * M(2 x 6) + M(5 x 3) * M(3 x 6) = 3 * 2 * 6 + 5 * 3 * 6

1번 식을 행렬로 표현해보면 다음과 같다.

1) M(5 x 3) * M(3 x 2) = M(5 x 3)을 만들 때 필요한 연산 + M(3 x 2)를 만들 때 필요한 연산 + (5 * 3 * 2)
2) M(5 x 2) * M(2 x 6) = M(5 x 2)를 만들 때 필요한 연산 + M(2 x 6)을 만들 때 필요한 연산 + (5 * 2 * 6)

1번 식을 만들기 위해 추가적으로 필요한 하위 문제는 M(5 x 2)이다.

 

2번 식을 행렬로 표현해보면 다음과 같다.

1) M(3 x 2) * M(2 x 6) = M(3 x 2)를 만들 때 필요한 연산 + M(2 x 6)을 만들 때 필요한 연산 + (3 * 2 * 6)
2) M(5 x 3) * M(3 x 6) = M(5 x 3)을 만들 때 필요한 연산 + M(3 x 6)을 만들 때 필요한 연산 + (5 * 3 * 6)

1번 식을 만들기 위해 추가적으로 필요한 하위 문제는 M(3 x 6)이다.

 

식 하나를 계산하기 위한 하위문제들이 발생한다.

따라서 Top-Down 방식으로 생각하는 것이 편하다.

private static int solve(int start, int end) {
    if (start == end) return dp[start][end] = 0;
    if (dp[start][end] != Integer.MAX_VALUE) return dp[start][end];

    for (int i = start; i < end; i++) {
        int ans = solve(start, i) + solve(i + 1, end) + (matrices[start].r * matrices[i].c * matrices[end].c);
        dp[start][end] = Math.min(dp[start][end], ans);
    }

    return dp[start][end];
}

start~end 행렬의 곱을 계산하는데 하위 문제들(M(start x mid) * M(mid x end))을 모두 구하고 오는 방식이다.