[백준] 11049번 행렬 곱셈 순서

문제 설명

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

문제 풀이

• 다이나믹 프로그래밍으로 풀이하였다. (백준 11066번과 유사)
• 문제 풀이에 사용된 점화식은 아래와 같다.

- DP[from][to] : from 인덱스에서 to 인덱스까지 행렬 곱셈 연산 수 
- arr[i][0] : i번쨰 행렬 row값, arr[i][1] : i번째 행렬 col값
- DP[from][to] = MIN(DP[from][i] + DP[i+1][to] + arr[from][0] * arr[i][1] * arr[to][1]) (from <= i < to)

소스 코드 (JAVA)

import java.io.*;

public class Main {
    public static int N;
    public static int INF = 987654321;
    public static int[][] arr = new int[500][2];
    public static int[][] dp = new int[500][500];

    public static void init() {
        for (int i = 0; i < N; i++) 
            for (int j = 0; j < N; j++) 
                dp[i][j] = INF;
    }

    public static int solve(int from, int to) {
        //기저조건 범위가 1개일 때 곱셈 0번
        if (from == to) return 0;
        if (dp[from][to] != INF) return dp[from][to];
        int result = INF;
        for (int i = from; i < to; i++) {
            result = Math.min(result, solve(from, i) + solve(i+1, to) + arr[from][0] * arr[i][1] * arr[to][1]);
        }
        return dp[from][to] = result;
    }

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

        N = Integer.parseInt(br.readLine());
        for (int i = 0; i < N; i++) {
            String[] input = br.readLine().split(" ");
            arr[i][0] = Integer.parseInt(input[0]);
            arr[i][1] = Integer.parseInt(input[1]);
        }
        init();
        bw.write(solve(0, N-1) + "\n");
        br.close();
        bw.flush();
        bw.close();
    }
}