[BOJ/DP] 백준 11049 - 행렬 곱셈 순서 (Java)

백준 11049 - 행렬 곱셈 순서

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

문제

크기가 NxM인 행렬 A, MxK인 B를 곱할 때 필요한 곱셈의 연산 수는 총 NxMxK번
행렬 N개를 곱하는데 필요한 곱셈의 연산 수는 행렬을 곱하는 순서에 따라 달라짐
ex. A의 크기 5x3, B의 크기 3x2, C의 크기 2x6인 경우 행렬 곱 ABC
- (AB)C_AB를 먼저 곱하고 C를 곱하는 경우: 5x3x2 + 5x2x6 = 30 + 60 = 90
- A(BC)_BC를 먼저 곱하고 A를 곱하는 경우: 3x2x6 + 5x3x6 = 36 + 90 = 126

입력 
첫째 줄: 행렬의 개수 N (1 <= N <= 500)
둘째 줄 ~ N개의 줄: 행렬의 크기 r, c (1 <= r, c <= 500)
항상 순서대로 곱셈을 할 수 있는 크기만 입력으로 주어짐
출력: 입력으로 주어진 행렬을 곱하는데 필요한 곱셈의 연산 최솟값 출력

---

풀이

`dp[i][j]`: i번째 행렬부터 j번째 행렬까지 곱하는 최소 연산 횟수

 

행렬을 k에서 나눔

• 왼쪽 계산 비용: `dp[i][k]`
• 오른쪽 계산 비용: `dp[k + 1][j]`
• 두 결과 곱하는 비용

(Ai ... Ak) x (A(k + 1) ... Aj)

• (Ai ... Ak) 결과 크기: rows[i] x cols[k]
• (A(k + 1) ... Aj) 결과 크기: rows[k + 1] x cols[j]

=> `rows[i] * cols[k] * cols[j]`

long cost = dp[i][k] + dp[k + 1][j] + (long) r[i] * c[k] * c[j];
dp[i][j] = Math.min(dp[i][j], cost);

 

길이가 `len`인 모든 구간 [i, j]를 하나씩 만듦

• `len`: 구간에 포함된 행렬의 개수
• 구간의 시작점: i
• 구간의 끝점: `j = i + len - 1` (인덱스는 1부터 시작)
• ex. len = 2: 행렬 2개짜리 구간
  • i = 1 / 포함되는 인덱스: [1, 2] / j = 2
  • i = 2 / 포함되는 인덱스: [2, 3] / j = 3

---

코드

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

// 행렬 곱셈 순서
public class boj_11049 {
    static int N;
    static int[] r, c;
    static long[][] dp;

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

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

        r = new int[N + 1];
        c = new int[N + 1];
        dp = new long[N + 1][N + 1];

        for (int i = 1; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            r[i] = Integer.parseInt(st.nextToken());
            c[i] = Integer.parseInt(st.nextToken());
        }

        for (int len = 2; len <= N; len++) {
            for (int i = 1; i + len - 1 <= N; i++) {
                int j = i + len - 1;
                dp[i][j] = Long.MAX_VALUE;

                for (int k = i; k < j; k++) {
                    long cost = dp[i][k] + dp[k + 1][j] + (long) r[i] * c[k] * c[j];
                    dp[i][j] = Math.min(dp[i][j], cost);
                }
            }
        }

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