← 다이아몬드 IV

크누스 최적화

사각 부등식으로 구간 DP를 O(N²)으로.

DP & 최적화

다이아몬드 IV

선수 지식: 구간 DP 분할 정복 최적화

1강 사각 부등식과 크누스 최적화 공식

대상 DP

구간 병합형 DP

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

는 최적 BST, 파일 합치기, 행렬 곱셈 순서 등에서 나온다. 정의대로 채우면 칸 $$O(n^2)$$ × 분기 $$O(n)$$ = $$O(n^3)$$ . 크누스 최적화는 비용 $$C$$ 가 적절한 조건을 만족할 때 이를 $$O(n^2)$$ 으로 줄인다.

두 가지 조건

$$C(i,j)$$ 가 다음을 만족한다고 하자.

사각 부등식(QI): $a\le b\le c\le d$ 에 대해
$C(a,c)+C(b,d) \le C(a,d)+C(b,c).$
단조성(MON): $a\le b\le c\le d$ 에 대해 $C(b,c)\le C(a,d)$ (구간이 포함되면 비용이 작거나 같음).

이 두 조건이 있으면 $$dp$$ 자체도 QI를 물려받고, 최적 분기점 $$opt[i][j]$$ (= $$dp[i][j]$$ 를 달성하는 $$k$$ ) 에 대해

$opt[i][j-1] \;\le\; opt[i][j] \;\le\; opt[i+1][j]$

가 성립한다. 즉 각 칸의 최적 분기점은 그 위·왼쪽 칸의 최적점 사이에 갇힌다.

왜 $$O(n^2)$$ 인가

길이 $\ell = j-i$ 가 같은 칸들을 한 줄로 보면, 그 줄의 분기점 탐색 총량은

$\sum_i \big(opt[i+1][j] - opt[i][j-1] + 1\big)$

이고, 인접 항의 상한·하한이 텔레스코핑으로 상쇄되어 줄 전체가 $$O(n)$$ 이 된다. 줄이 $$n$$ 개이므로 전체 $$O(n^2)$$ .

조건 검증

QI는 비용이 "구간 합"처럼 부분모듈러일 때 흔히 성립한다. 예를 들어 $C(i,j) = \big(\sum_{t=i}^{j} w_t\big)$ 같은 누적 비용은 QI와 MON을 동시에 만족한다. 확신이 없다면 작은 입력에서 brute로 $$opt$$ 단조성을 직접 확인하는 것이 안전하다.

다른 최적화와의 위치

최적화	DP 형태	결과
크누스	구간 $$dp[i][j]$$ , 분기 $\(i\le k$	$O(n^3)\to O(n^2)$
분할 정복	층 $dp[i][j]=\min_k dp[i-1][k]+C$	층당 $O(n\log n)$
CHT/Li Chao	비용이 직선	$O(\log)$ 전이

2강 크누스 최적화 구현과 응용 공식

표준 구현 (파일 합치기 / 최적 BST 골격)

$$C(i,j)$$ 는 보통 누적합으로 $$O(1)$$ . 길이가 짧은 구간부터 채우고, 분기 탐색 범위를 $opt[i][j-1]\dots opt[i+1][j]$ 로 제한한다.

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

int n;
ll w[2005];            // 가중치
ll pre[2005];          // 누적합
ll dp[2005][2005];     // dp[i][j]
int opt[2005][2005];   // 최적 분기점

ll cost(int i, int j) { return pre[j] - pre[i - 1]; }   // 구간 [i, j] 비용

ll knuth() {
    for (int i = 1; i <= n; i++) {
        dp[i][i] = 0;
        opt[i][i] = i;            // 길이 1 구간의 분기점
    }
    for (int len = 2; len <= n; len++) {
        for (int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            dp[i][j] = INF;
            int lo = opt[i][j - 1];
            int hi = opt[i + 1][j];   // 분기 탐색 범위 제한이 핵심
            for (int k = lo; k <= hi; k++) {
                ll val = dp[i][k] + dp[k + 1][j] + cost(i, j);
                if (val < dp[i][j]) {
                    dp[i][j] = val;
                    opt[i][j] = k;
                }
            }
        }
    }
    return dp[1][n];
}

자주 하는 실수

opt 경계 초기화. 길이 1 구간에서 opt[i][i]=i 를 설정하지 않으면 opt[i+1][j] 참조가 깨진다.
탐색 범위. 반드시 opt[i][j-1] 부터 opt[i+1][j] 까지. 범위를 넓게 잡으면 $$O(n^3)$$ 로 돌아가고, 좁게 잡으면 오답.
메모리. $$opt$$ 가 $$n^2$$ 정수라 $$n$$ 이 수천이면 메모리 한계를 확인한다. 필요하면 short/int 선택.
조건 미검증. QI/MON이 없으면 단조성이 깨져 틀린다.

응용

문제	비용 함수
파일/돌 합치기	구간 가중치 합
최적 이진 탐색 트리	접근 빈도 가중 깊이
구간 분할 비용	누적 비용 (QI 만족 시)

분할 정복 최적화와의 선택

DP가 "구간 병합 $dp[i][j]=\min_k dp[i][k]+dp[k+1][j]$ " 면 크누스, "층 누적 $dp[i][j]=\min_k dp[i-1][k]+C(k,j)$ " 면 분할 정복 최적화가 자연스럽다. 둘 다 QI에서 출발하지만 적용 구조가 다르다.