분할 정복 최적화

대상이 되는 DP 형태

다음과 같은 2차원 DP를 생각하자.

$$ dp[i][j] = \min_{k < j}\big(dp[i-1][k] + C(k, j)\big) $$

여기서 한 층(layer) \(i\)를 채우는 데 단순히 모든 \(k\)를 보면 \(O(n)\) 이라 한 층이 \(O(n^2)\), 전체 \(O(n^2 \cdot i)\) 가 든다. 분할 정복 최적화는 결정 단조성이 성립할 때 한 층을 \(O(n\log n)\) 으로 줄인다.

결정 단조성

\(opt[i][j]\) 를 \(dp[i][j]\) 를 최소화하는 최적 분기점 \(k\) 라 하자. 결정 단조성은

$$ j_1 < j_2 \;\Rightarrow\; opt[i][j_1] \le opt[i][j_2] $$

를 뜻한다. 즉 \(j\) 가 커지면 최적 분기점도 단조 증가(또는 단조 감소)한다. 이것이 성립하면 가운데 \(j_m=(lo+hi)/2\) 의 최적점을 직접 찾았을 때, 왼쪽 절반은 \(opt \le opt[i][j_m]\), 오른쪽 절반은 \(opt \ge opt[i][j_m]\) 범위에서만 탐색하면 된다.

비용 함수의 조건 (Quadrangle Inequality)

\(C\) 가 사각 부등식(QI)

$$ C(a,c)+C(b,d) \le C(a,d)+C(b,c) \quad (a\le b\le c\le d) $$

를 만족하면 결정 단조성이 따라온다. 직관적으로 "구간이 교차하는 것보다 포함하는 편이 싸다"는 성질이다. 실전에서는 비용이 면적·거리·로그 합처럼 볼록할 때 자주 성립한다.

분할 정복으로 한 층 채우기

solve(lo, hi, optlo, opthi) 는 \(j\in[lo,hi]\) 를 채우며 그 최적점이 \([optlo,opthi]\) 안에 있음을 안다.

1. \(mid = (lo+hi)/2\) 에 대해 \(k\in[optlo,\min(mid,opthi)]\) 를 전부 보며 \(dp[i][mid]\) 와 \(opt[i][mid]=best\) 를 직접 계산.
2. solve(lo, mid-1, optlo, best), solve(mid+1, hi, best, opthi) 로 재귀.

각 깊이에서 보는 \(k\) 의 총량이 \(O(n)\), 깊이가 \(O(\log n)\) 이므로 한 층 \(O(n\log n)\).

복잡도와 적용 가능성 판단

증명이 어렵다면 작은 입력에서 brute force와 결정 단조성을 직접 검증해 보는 실험적 확인이 흔히 쓰인다.

표준 구현

k개의 그룹으로 나누는 비용 최소화(예: 막대를 \(R\) 구간으로 분할)에서, 한 층씩 분할 정복으로 채운다.

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

int n, R;
vector<vector<ll>> dp;   // dp[i][j]: j개 원소를 i구간으로
ll cost(int l, int r);   // 구간 [l, r]의 비용 (보통 누적합으로 O(1))

// i번째 층을 채운다. j는 [lo, hi], 최적점은 [optlo, opthi]에 있다.
void solve(int i, int lo, int hi, int optlo, int opthi) {
    if (lo > hi) return;
    int mid = (lo + hi) / 2;
    pair<ll, int> best = {INF, -1};
    int up = min(mid, opthi);
    for (int k = optlo; k <= up; k++) {
        ll val = dp[i - 1][k] + cost(k, mid - 1);
        best = min(best, {val, k});
    }
    dp[i][mid] = best.first;
    int opt = best.second;
    solve(i, lo, mid - 1, optlo, opt);
    solve(i, mid + 1, hi, opt, opthi);
}

ll partition_dp() {
    dp.assign(R + 1, vector<ll>(n + 1, INF));
    dp[0][0] = 0;
    for (int i = 1; i <= R; i++)
        solve(i, 1, n, 0, n);     // j는 1..n, 분기 k는 0..n
    return dp[R][n];
}

자주 하는 실수

• 인덱스 경계. cost(k, mid-1) 에서 \(k\) 는 "앞 구간의 끝+1", 즉 새 구간이 \([k, mid-1]\) 인지 \([k+1, mid]\) 인지 정의를 한 번만 정하고 일관되게 쓴다.
• opt 범위 전달 오류. 왼쪽엔 (optlo, opt), 오른쪽엔 (opt, opthi) 를 넘긴다. 닫힌 구간을 겹치게 넘겨야 mid 자신의 최적점을 놓치지 않는다.
• 단조성이 없는데 적용. QI를 확인하지 않으면 오답이 난다. 의심되면 brute와 비교 검증.
• 누적합 미사용. cost가 \(O(1)\) 이 아니면 전체 복잡도가 한 단계 더 곱해진다.

응용

다른 최적화와의 관계

크누스 최적화 역시 QI에서 출발하지만 층 구조가 아니라 구간 DP \(dp[i][j]\) 에서 \(opt[i][j-1]\le opt[i][j]\le opt[i+1][j]\) 를 이용해 전체를 \(O(n^2)\) 로 만든다. 본 단원의 DnC는 "층마다 한 차원이 1씩 증가"하는 구조에 맞는다. CHT/Li Chao 트리는 비용이 직선(\(a_k\ x + b_k\)) 형태일 때 더 일반적으로 쓸 수 있다.