[DP] 구간(Interval) DP (백준 11049)

목차

• 1. 서론: 왜 행렬 곱셈 순서가 중요한가?
• 2. 선형 DP vs 구간 DP
• 3. ‘이건 구간 DP다’ 냄새 맡는 법
• 4. 3중 루프의 필승 공식
• 5. 최종 구현 및 코드 분석
• 6. 결론: 분할 정복과 메모이제이션의 만남

1. 서론: 왜 행렬 곱셈 순서가 중요한가?

행렬의 곱셈은 결합 법칙이 성립합니다. 즉, (AB)C와 A(BC)의 연산 결과 행렬은 같습니다. 하지만 컴퓨터 입장에서 이 둘은 천지 차이입니다. 연산 횟수(Scalar Multiplication)가 달라지기 때문입니다.

예를 들어 A(5×3), B(3×100), C(100×1) 행렬이 있다고 가정해 봅시다.

• (AB)C: (5x3x100) + (5x100x1) = 1,500 + 500 = 2,000회
• A(BC): (3x100x1) + (5x3x1) = 300 + 15 = 315회

순서만 바꿨을 뿐인데 연산량이 6배 이상 차이가 납니다. 행렬의 개수가 많아질수록 이 차이는 기하급수적으로 커지며, 잘못된 순서로 계산하면 슈퍼컴퓨터도 멈추게 만들 수 있습니다. 백준 11049번은 바로 이 ‘최적의 괄호 묶기’를 찾는 문제입니다.

2. 선형 DP vs 구간 DP

많은 입문자가 이 문제를 접했을 때 기존의 DP(선형 DP) 방식으로 접근하다 좌절합니다. 두 방식은 사고의 구조 자체가 다릅니다.

선형 DP (Linear DP)

LIS(최장 증가 부분 수열)나 계단 오르기 문제는 선형적입니다. dp[i]를 구할 때 dp[i-1] 혹은 dp[i-2]를 참고합니다. 즉, “과거의 나”가 “현재의 나”를 만듭니다. 도미노가 순서대로 쓰러지는 것과 같습니다.

구간 DP (Interval DP)

반면, 행렬 곱셈이나 파일 합치기 같은 구간 DP는 입체적입니다. dp[i][j](i부터 j까지의 최적해)를 구하기 위해, 우리는 i와 j 사이의 어딘가 k를 기준으로 뚝 잘라봐야 합니다. 즉, “내 내부의 분열(Split)”을 관찰해야 합니다. 이는 토너먼트 대진표를 짜거나, 러시아 인형(마트료시카)을 조립하는 과정과 유사합니다.

핵심은 “큰 구간을 계산하기 전에, 그 안의 작은 구간들이 이미 계산되어 있어야 한다”는 것입니다.

3. ‘이건 구간 DP다’ 냄새 맡는 법

코딩 테스트 현장에서 이 문제가 구간 DP임을 어떻게 눈치챌 수 있을까요? 다음 3가지 시그널(Signal)이 감지되면 강력하게 의심해야 합니다.

Signal 1: 인접 결합 (Adjacency)

문제에서 “인접한 것끼리만 합칠 수 있다”거나 “순서를 섞을 수 없다(Sort 불가)”는 조건이 있다면 90%입니다. 행렬 곱셈, 파일 합치기, 팰린드롬 만들기 등이 이에 해당합니다. 멀리 떨어져 있는 요소를 가져올 수 없고, 반드시 껍질(인접 요소)이 벗겨져야 만날 수 있는 구조입니다.

Signal 2: 중간 상태의 영향력 (State Dependency)

단순히 비용을 더하는 것을 넘어, “내가 만든 덩어리의 결과 상태가 다음 연산 비용을 결정”하는 경우입니다. 행렬 곱셈에서 (AB)의 결과 행렬 크기가 나중에 C와 곱할 때의 비용을 결정하는 것이 대표적입니다.

Signal 3: N = 500 (Time Complexity)

이것은 메타적인 힌트입니다. 구간 DP는 필연적으로 3중 루프를 사용하므로 시간 복잡도가 O(N³)입니다. 현대 컴퓨터가 1초에 약 1억 번 연산한다고 할 때, 500³은 1.25억으로 제한 시간(1~2초)에 아슬아슬하게 들어옵니다. 만약 N이 10만이라면 그리디나 선형 DP겠지만, N이 500 이하라면 구간 DP를 강력히 의심해보세요.

4. 3중 루프의 필승 공식

구간 DP 문제는 점화식보다 반복문의 순서가 더 중요합니다. 반드시 다음 순서를 지켜야 합니다.

Step 1: 길이 (Length) – “작은 것부터”

가장 바깥쪽 루프는 구간의 길이입니다. 길이 2짜리(인접한 두 행렬 곱)를 다 구하고, 그 정보를 이용해 길이 3짜리를 구하는 식입니다.

Step 2: 시작점 (Start) – “어디서부터”

중간 루프는 시작점 i입니다. j(끝점)는 i + length - 1로 자동 결정됩니다.

Step 3: 분할점 (Split Point) – “어디를 자를까”

가장 안쪽 루프는 분할점 k입니다. i부터 j-1까지 순회하며 최적의 절단 위치를 찾습니다.

// 구간 DP 공식 템플릿
for (int len = 2; len <= n; len++) {       // 1. 길이
    for (int i = 0; i <= n - len; i++) {   // 2. 시작점
        int j = i + len - 1;               //    끝점 (자동)
        dp[i][j] = Integer.MAX_VALUE;
        
        for (int k = i; k < j; k++) {      // 3. 분할점
            // 점화식: 왼쪽 덩어리 + 오른쪽 덩어리 + 합치는 비용
            int cost = dp[i][k] + dp[k+1][j] + (m[i][0]*m[k][1]*m[j][1]);
            dp[i][j] = Math.min(dp[i][j], cost);
        }
    }
}

5. 최종 구현 및 코드 분석

위 공식을 백준 11049번에 적용한 최종 Java 코드입니다.

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

class Main {
    static int n;
    static int[][] m; // 행렬의 크기 정보 (행, 열)
    static int[][] dp; // dp[i][j]: i번 행렬부터 j번 행렬까지 곱하는 최소 연산 횟수

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        
        m = new int[n][2];
        dp = new int[n][n];

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            m[i][0] = Integer.parseInt(st.nextToken());
            m[i][1] = Integer.parseInt(st.nextToken());
        }

        // [구간 DP 공식 적용]
        
        // 1. 길이 (len): 2개부터 N개까지 덩어리 크기를 키워감
        // len이 1인 경우(행렬 1개)는 연산 횟수가 0이므로 초기화 불필요 (int 기본값 0)
        for (int len = 1; len < n; len++) {
            
            // 2. 시작점 (i): 0번부터 시작
            for (int i = 0; i < n - len; i++) {
                int j = i + len; // 끝점 (j) 설정
                
                dp[i][j] = Integer.MAX_VALUE; // 최솟값 갱신을 위해 MAX 초기화

                // 3. 분할점 (k): i부터 j-1까지 자를 수 있는 모든 곳을 탐색
                for (int k = i; k < j; k++) {
                    // 비용 = (왼쪽 부분 최적해) + (오른쪽 부분 최적해) + (두 덩어리 합치는 비용)
                    // m[i][0]: 왼쪽 행렬의 행
                    // m[k][1]: 왼쪽 행렬의 열 (== 오른쪽 행렬의 행)
                    // m[j][1]: 오른쪽 행렬의 열
                    int cost = dp[i][k] + dp[k+1][j] + (m[i][0] * m[k][1] * m[j][1]);
                    
                    if (cost < dp[i][j]) {
                        dp[i][j] = cost;
                    }
                }
            }
        }

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

6. 결론: 분할 정복과 메모이제이션의 만남

백준 11049번은 단순한 계산 문제가 아닙니다. “문제를 쪼개서(Divide)” 해결하고, 그 결과를 “저장(Memoization)”하여 다시 사용하는 알고리즘의 본질을 꿰뚫는 문제입니다.

처음에는 3중 루프가 낯설고 어렵게 느껴질 수 있습니다. 하지만 “길이 → 시작점 → 분할점”이라는 공식은 이 유형의 모든 문제(파일 합치기, 팰린드롬 등)에 통용되는 만능 열쇠입니다. 이제 여러분은 N=500과 인접 연산이라는 힌트만 봐도 “아, 이건 구간 DP구나!”라고 자신 있게 외칠 수 있습니다.