BOJ#11049 행렬 곱셈 순서

BOJ#11049 행렬 곱셈 순서

* 문제

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

* 풀이

비슷한 문제 : 파일 합치기 https://www.acmicpc.net/problem/11066

행렬은 결합법칙이 성립합니다. (AB)C = A(BC)

그러나 순서에 따라 곱셈 횟수는 달라집니다.

문제 풀이 방식은 파일 합치기 문제와 동일합니다.

dp[start][end] = min(dp[start][end], dp[start][k] + dp[k+1][j] + (d_start * d_k+1 * d_end+1)),  i <= k < end

3
5 3
3 2
2 6

위 예제에서

d_0 = 5

d_1 = 3

d_2 = 2

d_3 = 6

* 나의 코드

https://github.com/stack07142/BOJ/blob/e764b2d7fe041a5d170673f99cc6d4d2ba338157/BOJ%2311049/src/Main.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    static int N;
    static int[] D = new int[501];
    static int[][] dp = new int[501][501];

    static final int MAX_VALUE = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {

        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++) {

            StringTokenizer st = new StringTokenizer(br.readLine());

            D[i] = Integer.parseInt(st.nextToken());
            D[i + 1] = Integer.parseInt(st.nextToken());

            Arrays.fill(dp[i], MAX_VALUE);
        }

        // Solve

        System.out.println(solve(0, N - 1));

    }

    static int solve(int start, int end) {

        if (start == end) return 0;

        if (dp[start][end] != MAX_VALUE) return dp[start][end];

        for (int i = start; i < end; i++) {

            dp[start][end] = Math.min(dp[start][end], solve(start, i) + solve(i + 1, end) + D[start] * D[i + 1] * D[end + 1]);
        }

        return dp[start][end];
    }
}