백준 11049 행렬 곱셈 순서 Java: 구간 DP 점화식 도출

백준 11049번 ‘행렬 곱셈 순서’는 행렬의 순서를 바꾸지 않고 괄호를 어디에 칠지 정해 scalar multiplication 횟수를 최소화하는 문제다. A×B×C의 결과는 같아도 (A×B)×C와 A×(B×C)의 계산량은 다르다.

• 백준 11049번 행렬 곱셈 순서

DP 상태를 구간으로 잡는다

dp[start][end]를 start번부터 end번 행렬까지 곱하는 최소 비용으로 둔다. 마지막 곱셈 직전에 구간을 start..middle과 middle+1..end로 나눴다고 생각하면 세 비용이 필요하다.

1. 왼쪽 구간을 하나의 행렬로 만드는 비용
2. 오른쪽 구간을 하나의 행렬로 만드는 비용
3. 완성된 두 행렬을 마지막으로 곱하는 비용

행렬 i의 크기를 row[i] × column[i]라고 하면 점화식은 다음과 같다.

dp[start][end]
= min(
    dp[start][middle]
    + dp[middle + 1][end]
    + row[start] × column[middle] × column[end]
  )

모든 middle을 시도해 가장 작은 값을 고른다. 행렬 하나만 있는 구간은 곱셈이 필요 없으므로 dp[i][i] = 0이다.

작은 예제로 비용 비교하기

행렬 크기가 차례로 5×3, 3×2, 2×6이라고 하자.

(A × B) × C = 5×3×2 + 5×2×6 = 30 + 60 = 90
A × (B × C) = 3×2×6 + 5×3×6 = 36 + 90 = 126

두 방식의 결과 행렬은 모두 5×6이지만 첫 번째 순서가 더 적은 연산을 사용한다. 구간 DP는 이 비교를 모든 부분 구간에 대해 저장한다.

Java 코드

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(
                new InputStreamReader(System.in)
        );

        int matrixCount = Integer.parseInt(reader.readLine());
        int[] row = new int[matrixCount];
        int[] column = new int[matrixCount];

        for (int index = 0; index < matrixCount; index++) {
            StringTokenizer tokenizer = new StringTokenizer(
                    reader.readLine()
            );
            row[index] = Integer.parseInt(tokenizer.nextToken());
            column[index] = Integer.parseInt(tokenizer.nextToken());
        }

        long[][] dp = new long[matrixCount][matrixCount];

        for (int length = 2; length <= matrixCount; length++) {
            for (
                    int start = 0;
                    start + length <= matrixCount;
                    start++
            ) {
                int end = start + length - 1;
                dp[start][end] = Long.MAX_VALUE;

                for (int middle = start; middle < end; middle++) {
                    long mergeCost = (long) row[start]
                            * column[middle]
                            * column[end];

                    dp[start][end] = Math.min(
                            dp[start][end],
                            dp[start][middle]
                                    + dp[middle + 1][end]
                                    + mergeCost
                    );
                }
            }
        }

        System.out.println(dp[0][matrixCount - 1]);
    }
}

이미 계산된 짧은 구간을 건드리지 않고 지금 구하는 dp[start][end]만 Long.MAX_VALUE로 초기화한다. 곱셈 세 항은 long으로 올린 뒤 계산해 intermediate overflow를 피했다.

계산 순서와 복잡도

긴 구간을 계산하려면 그보다 짧은 왼쪽·오른쪽 구간의 답이 먼저 필요하다. 그래서 구간 길이를 2부터 늘린다.

• 상태 수: O(N²)
• 한 상태에서 확인하는 분할점: O(N)
• 전체 시간: O(N³)
• DP table 공간: O(N²)

3~4일 막혔던 기록

원문에는 이 문제를 3일 또는 4일가량 생각했다고 적혀 있다. 백준 11066 파일 합치기와 비슷한 구간 DP라는 점은 알았지만 점화식이 나오지 않아 답답했고, 영화를 본 뒤 카페에 가서야 분할점을 기준으로 두 구간과 마지막 곱셈 비용을 합치는 구조가 보였다.

두 문제의 차이는 마지막 비용이다. 파일 합치기는 start..end 파일 크기의 총합을 더하고, 행렬 곱셈은 분할점에서 만들어진 두 행렬의 차원을 곱한다. “마지막 연산 직전 상태”를 그려 보면 점화식이 훨씬 덜 추상적으로 느껴진다.

검증 범위

Java source를 수동 검토하고 행렬 1개, 2개, 세 행렬의 두 parenthesization과 작은 random chain을 모든 괄호 경우를 열거하는 oracle과 대조한다. 현재 환경에는 실제 JDK가 없어 compile·judge 재제출은 live 반영 전에 별도 확인이 필요하다.