구간 DP

어떤 문제를 푸는가

수열이나 구간을 다룰 때, "구간 \([l, r]\)의 답"을 그 안의 어떤 경계 \(k\)에서
둘로 쪼개 작은 구간의 답으로 정의하는 DP입니다. 행렬 곱셈 순서, 돌 합치기,
팰린드롬 분할 같은 "어디서 나눌까/합칠까"가 핵심인 문제에 쓰입니다.

상태와 점화식의 골격

$$ dp[l][r] = \text{구간 } [l, r] \text{을 처리하는 최적 비용} $$

길이 1(또는 0) 구간은 기저로 직접 채우고, 더 긴 구간은 가능한 분할점 \(k\)를
모두 시도해 최적을 고릅니다.

$$ dp[l][r] = \min_{l \le k < r} \bigl( dp[l][k] + dp[k+1][r] + (\text{합치는 비용}) \bigr) $$

"합치는 비용"은 문제마다 다릅니다(예: 두 묶음의 합, 행렬 곱셈의 연산 수).

예 — 돌 합치기 / 파일 합치기

연속한 두 묶음을 합치는 비용이 "두 묶음 크기의 합"일 때, 전부 하나로 합치는
최소 비용을 구합니다. 구간 \([l, r]\)의 합 \(S(l, r)\)은 누적 합으로 \(O(1)\)에
구하고,

$$ dp[l][r] = \min_{l \le k < r} \bigl( dp[l][k] + dp[k+1][r] \bigr) + S(l, r) $$

마지막 합치기 비용 \(S(l, r)\)은 어디서 나누든 동일하게 더해집니다.

왜 옳은가

최적해의 구조를 보면, 구간 \([l, r]\)을 최종적으로 만드는 마지막 합치기/분할
이 어딘가의 경계 \(k\)에서 일어납니다. 그 \(k\)로 나눈 두 부분은 각각 자신의
최적해여야 합니다(아니면 전체를 개선할 수 있으므로). 모든 \(k\)를 시도하면 그중
진짜 최적 경계가 포함되므로 최적 부분 구조가 성립합니다.

채우는 순서 — 길이 오름차순

dp[l][r]은 자기보다 짧은 구간들에 의존합니다. 따라서 구간 길이를 1부터
키워 가며 채워야 의존하는 값이 먼저 준비됩니다.

for len = 2..n:
    for l = ...:
        r = l + len - 1
        dp[l][r] = min over k

복잡도

구간 쌍 \(O(N^2)\)개, 각 구간마다 분할점 \(O(N)\)이므로

$$ O(N^3) $$

\(N \le 400 \sim 500\) 정도에서 현실적입니다. 사각 부등식이 성립하면
크누스 최적화로 \(O(N^2)\)까지 줄일 수 있습니다(상위 단원).

신호 잡기

"구간을 어디서 나눌까/합칠까", "양 끝에서 어떻게 좁힐까"가 문제의 본질이고
\(N\)이 수백 규모면 구간 DP를 의심하세요. 다음 강의에서 구현과 변형을 봅니다.

돌 합치기 구현 (C++)

길이를 키우며 채우고, 누적 합으로 구간 합을 \(O(1)\)에 얻습니다.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;

int main() {
    int n; cin >> n;
    vector<ll> a(n + 1), pre(n + 1, 0);
    for (int i = 1; i <= n; i++) { cin >> a[i]; pre[i] = pre[i - 1] + a[i]; }
    auto S = [&](int l, int r) { return pre[r] - pre[l - 1]; };

    vector<vector<ll>> dp(n + 1, vector<ll>(n + 1, 0));   // 길이1은 0
    for (int len = 2; len <= n; len++) {
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            dp[l][r] = INF;
            for (int k = l; k < r; k++)
                dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]);
            dp[l][r] += S(l, r);          // 마지막 합치기 비용
        }
    }
    cout << dp[1][n] << '\n';
}

행렬 곱셈 순서 (변형)

행렬 \(A_1 \cdots A_n\)을 곱하는 최소 스칼라 곱셈 수. 행렬 \(i\)의 크기가
\(p_{i-1} \times p_i\)일 때,

$$ dp[l][r] = \min_{l \le k < r} \bigl( dp[l][k] + dp[k+1][r] + p_{l-1}\,p_k\,p_r \bigr) $$

"합치는 비용"이 합이 아니라 곱셈 횟수 \(p_{l-1} p_k\ p_r\)로 바뀐 것뿐, 골격은
동일합니다.

파이썬 구현 (돌 합치기)

import sys
input = sys.stdin.readline

n = int(input())
a = [0] + [int(input()) for _ in range(n)]
pre = [0] * (n + 1)
for i in range(1, n + 1):
    pre[i] = pre[i - 1] + a[i]

INF = float('inf')
dp = [[0] * (n + 1) for _ in range(n + 1)]
for length in range(2, n + 1):
    for l in range(1, n - length + 2):
        r = l + length - 1
        best = INF
        for k in range(l, r):
            best = min(best, dp[l][k] + dp[k + 1][r])
        dp[l][r] = best + pre[r] - pre[l - 1]
print(dp[1][n])

파이썬 \(O(N^3)\)는 \(N\)이 수백을 넘으면 위태로우니 필요 시 C++로.

흔한 함정

• 채우는 순서 — 길이 오름차순이 아니면 의존 값이 준비되지 않아 틀립니다.
  이 단원 최다 실수.
• 기저 초기화 — 길이 1 구간 값(보통 0)을 정확히. "정확히 채워야"면 도달
  불가를 \(\infty\)로 둘 수도.
• 분할점 범위 — k는 l <= k < r. 끝 포함 여부 off-by-one 주의.
• 구간 합 자료형 — 누적 합과 dp 모두 long long.
• 원형(circular) — 원형으로 합치는 변형은 배열을 두 배로 늘려 길이 \(n\)
  구간들만 보거나, 시작점을 \(O(N)\)번 돌립니다.

응용 패턴

• 합치기/쪼개기 비용 최소화 — 돌·파일 합치기.
• 곱셈/연산 순서 — 행렬 곱셈, 괄호 매기기.
• 팰린드롬/문자열 분할 — 양 끝 글자 일치로 구간을 좁힘.
• 양 끝에서 진행하는 게임 — 두 플레이어가 양 끝에서 집어가는 최적 전략.

"구간을 경계 \(k\)로 나눠 작은 구간의 답을 합친다"는 한 문장과 "길이 오름차순
채우기"만 손에 익히면, 겉보기에 다른 문제들이 같은 골격으로 보이기 시작합니다.

출제 신호

• "연속한 것들을 합치거나 제거하며 비용/점수를 최적화" — 파일 합치기,
  행렬 곱셈 순서, 돌 합치기, 풍선 터뜨리기
• "팰린드롬인지/팰린드롬으로 만드는" 질의·분할 문제
• "괄호 문자열, 양 끝에서 안쪽으로 결정되는 구조"
• 제약 신호: \(N \le 500\) 안팎 — 구간 쌍 \(O(N^2)\) \(\times\) 분할점 \(O(N)\) =
  \(O(N^3)\)이 허용되는 크기. \(N \le 100\)이면 더 확실합니다.

판별 질문: "구간 \([i, j]\)의 답이, 그 내부 분할 \([i, k] + [k+1, j]\) (또는
양 끝 문자 비교 후 \([i+1, j-1]\))의 답으로 조립되는가?" — 그렇다면 구간 DP입니다.

풀이 결정 절차

1. 상태를 적습니다 — dp[i][j] = "구간 \([i, j]\)만 남았을 때의 최적값".
2. 전이 종류를 고릅니다 — (a) 분할형: \(\min_k(dp[i][k] + dp[k+1][j] + \text{결합 비용})\),
   (b) 양끝형: s[i] == s[j]이면 dp[i+1][j-1]에서.
3. 기저를 적습니다 — 길이 1(dp[i][i]), 필요시 길이 2까지 직접 채웁니다.
4. 복잡도 검산 — \(O(N^3)\)이 시간 안인지, 결합 비용(예: 구간 합)은 누적 합으로
   \(O(1)\)에 꺼낼 수 있게 준비합니다.

자주 하는 실수

가장 흔한 구조적 버그는 계산 순서입니다. dp[i][j]는 자기보다 짧은
구간들이 모두 계산된 뒤에야 만들 수 있으므로, 루프는 반드시
구간 길이 오름차순이어야 합니다. \(i, j\) 이중 for 문을 무심코 돌리면
아직 빈 칸을 읽습니다.

# 파일 합치기형: 길이부터 돈다
for length in range(2, n + 1):
    for i in range(1, n - length + 2):
        j = i + length - 1
        dp[i][j] = min(
            dp[i][k] + dp[k + 1][j]
            for k in range(i, j)
        ) + prefix[j] - prefix[i - 1]     # 이번 병합 비용 = 구간 합

• 기저 초기화 실수 — 분할형에서 dp[i][i] = 0(혼자면 비용 없음)인지,
  문제에 따라 길이 1에 비용이 있는지 확인하세요. 팰린드롬형은 길이 1 = 참,
  길이 2 = s[i] == s[j]를 직접 채워야 dp[i+1][j-1] 참조(빈 구간)가
  안전해집니다.
• 결합 비용을 매번 루프로 계산 — 구간 합을 분할점마다 다시 더하면
  \(O(N^4)\)가 됩니다. 누적 합 전처리가 사실상 필수입니다.
• 분할점 범위 — \(k\)는 \(i \le k < j\). k = j까지 돌리면 빈 구간
  dp[j+1][j]를 읽습니다. 그런 칸을 0으로 깔아 두면 버그가 조용히 숨으니
  범위를 정확히 끊는 편이 낫습니다.
• 메모이제이션 재귀의 한도 — 파이썬 재귀 구현은 \(N = 500\)이면 깊이는
  괜찮지만 호출 횟수(\(N^2\) 상태)로 느려질 수 있어, 반복문(길이 루프)이 안전합니다.
• 원형 배열 변형 — 돌이 원형으로 놓이면 배열을 두 배로 이어 붙여
  길이 \(N\) 구간을 보거나, 첫 결정을 고정해 선형으로 환원합니다.

연습 방법

사이드바 연습 목록의 파일 합치기(분할형)와 팰린드롬 질의(양끝형)를 먼저
하나씩 풀어 두 전이 유형을 분리해서 익히세요. 그다음 행렬 곱셈 순서, 원형
변형으로 확장합니다. 새 문제에서는 "상태 / 전이 / 기저 / 길이 루프" 네 줄을
코드보다 먼저 쓰는 습관이 구간 DP를 안정시킵니다. 태그된 문제 3문제 이상
해결 시 마스터 처리되어 레이팅 CLASS 보너스에 반영됩니다.