분할정복 DP 최적화 (Divide and Conquer Optimization)

정의

분할정복 DP 최적화 (Divide and Conquer Optimization) 는 dp[i][j] = min(dp[i-1][k] + C[k+1][j]) 꼴의 DP 에서, 최적 분할점 opt[i][j] 가 j 에 대해 단조 비감소 (opt[i][j] <= opt[i][j+1]) 일 때, 분할정복으로 k 탐색 범위를 제한해 시간 복잡도를 O(K N^2) 에서 O(K N log N) 으로 줄이는 기법.

문제 상황과 동기

왜 필요한가

N 개의 원소를 K 개의 그룹으로 나누는 DP:

dp[k][i] = min (dp[k-1][j] + cost(j+1, i))   (0 <= j < i)

• naive: 각 dp[k][i] 마다 모든 j 검사. O(K * N^2). N=10^5, K=10 이면 10^11.
• D&C 최적화: opt[i] 단조성을 이용, O(K * N log N). 10^5 * log(10^5) * 10 ≈ 2*10^7, 통과.

핵심 통찰: j 의 후보 범위가 단조적이면, 분할정복으로 각 레이어를 O(N log N) 에 채울 수 있다. 전체 문제를 mid 에서의 최적 j 를 찾은 후, 좌/우 반쪽의 j 후보 범위를 각각 [optL, bestK] 와 [bestK, optR] 로 좁혀 재귀한다.

전제 조건

cost(l, r) 가 다음 사각 부등식 (quadrangle inequality) 을 만족하면 opt[i] 가 단조 비감소한다.

cost(a, c) + cost(b, d) <= cost(a, d) + cost(b, c)   (a <= b <= c <= d)

시각화

핵심 아이디어

Opt[i] 가 단조 비감소 (opt[i] <= opt[i+1]) 라면, j 후보 범위를 재귀적으로 좁혀도 안전하다.

dc(k, l, r, optL, optR):
    if l > r: return
    mid = (l + r) / 2
    bestK = optL
    bestVal = INF
    for j = optL .. min(mid-1, optR):
        val = dp[k-1][j] + cost(j+1, mid)
        if val < bestVal:
            bestVal = val
            bestK = j
    dp[k][mid] = bestVal
    dc(k, l, mid-1, optL, bestK)      # 왼쪽: j 범위 [optL, bestK]
    dc(k, mid+1, r, bestK, optR)      # 오른쪽: j 범위 [bestK, optR]

각 레이어 k 에서 모든 호출의 j 순회 합 = O(N log N). (N 개 원소 각각이 log N 번 방문)

알고리즘

DnCDP(a[1..N], K):
    dp[0][0] = 0
    for i = 1..N:
        dp[1][i] = cost(1, i)     # 1개 그룹
    
    for k = 2..K:
        solve(k, 1, N, 0, N)      # 분할정복
    
    return dp[K][N]

solve(k, l, r, optL, optR):
    if l > r: return
    mid = (l + r) / 2
    bestK = optL
    bestVal = INF
    for j = optL .. min(mid-1, optR):
        val = dp[k-1][j] + cost(j+1, mid)
        if val < bestVal:
            bestVal = val
            bestK = j
    dp[k][mid] = bestVal
    solve(k, l, mid-1, optL, bestK)
    solve(k, mid+1, r, bestK, optR)

구현

다음은 배열을 K 개 그룹으로 나누고 각 그룹 합의 제곱을 최소화하는 문제. cost(l, r) = (prefix[r] - prefix[l-1])^2.

// D&C Optimization: O(K N log N), cost = (sum)^2
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
​
int N, K;
vector<ll> a, ps;
vector<vector<ll>> dp;
​
ll cost(int l, int r) {
  ll s = ps[r] - ps[l - 1];
  return s * s;
}
​
void dac(int k, int l, int r, int optL, int optR) {
  if (l > r) return;
  int mid = (l + r) / 2;
  int bestK = optL;
  ll bestVal = INF;
  for (int j = optL; j <= min(mid - 1, optR); j++) {
      ll val = dp[k - 1][j] + cost(j + 1, mid);
      if (val < bestVal) {
          bestVal = val;
          bestK = j;
      }
  }
  dp[k][mid] = bestVal;
  dac(k, l, mid - 1, optL, bestK);
  dac(k, mid + 1, r, bestK, optR);
}
​
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> N >> K;
  a.resize(N + 1);
  ps.resize(N + 1);
  for (int i = 1; i <= N; i++) {
      cin >> a[i];
      ps[i] = ps[i - 1] + a[i];
  }
  dp.assign(K + 1, vector<ll>(N + 1, INF));
  dp[0][0] = 0;
  for (int i = 1; i <= N; i++)
      dp[1][i] = cost(1, i);
  for (int k = 2; k <= K; k++)
      dac(k, 1, N, 0, N);
  cout << dp[K][N] << '
';
}

import sys
sys.setrecursionlimit(1 << 25)
input = sys.stdin.readline
INF = 10 ** 18
​
N, K = map(int, input().split())
a = [0] + list(map(int, input().split()))
ps = [0] * (N + 1)
for i in range(1, N + 1):
  ps[i] = ps[i - 1] + a[i]
​
def cost(l, r):
  s = ps[r] - ps[l - 1]
  return s * s
​
dp = [[INF] * (N + 1) for _ in range(K + 1)]
dp[0][0] = 0
​
def dac(k, l, r, optL, optR):
  if l > r:
      return
  mid = (l + r) // 2
  best_k = optL
  best_val = INF
  for j in range(optL, min(mid, optR + 1)):
      val = dp[k - 1][j] + cost(j + 1, mid)
      if val < best_val:
          best_val = val
          best_k = j
  dp[k][mid] = best_val
  dac(k, l, mid - 1, optL, best_k)
  dac(k, mid + 1, r, best_k, optR)
​
for i in range(1, N + 1):
  dp[1][i] = cost(1, i)
​
for k in range(2, K + 1):
  dac(k, 1, N, 0, N)
​
print(dp[K][N])

4 2
1 2 3 4

52

5 2
1 3 2 4 2

72

복잡도

amortized 분석

solve(k, 1, N, 0, N) 호출의 j 순회 횟수: 각 레벨마다 O(N) 합, 깊이 log N. 총 O(N log N). K 개 레이어 곱하면 O(K N log N).

변형 / 활용

D&C 최적화는 K 가 작을 때 (K ≤ N) 특히 효과적. K = sqrt(N) 정도까지는 O(N sqrt(N) log N) 으로 양호.

함정

1. cost() 가 O(1) 이 아닌 경우

cost(l, r) 를 O(1) 에 계산할 수 있어야 한다. prefix sum 으로 충분한 cost 함수가 이상적. O(log N) 짜리 cost 면 전체 O(K N log^2 N).

2. opt 단조성 증명 없이 사용

사각 부등식을 만족하지 않는 cost 함수에 적용하면 답이 틀리거나 더 느려짐. cost = (prefix[r] - prefix[l-1])^2 는 만족하지만, cost = abs(prefix[r] - prefix[l-1]) 는 일반적으로 불만족.

3. 재귀 깊이

N=10^5 일 때 재귀 깊이는 log N ≈ 17. 안전하지만 스택 메모리 확인. Python 은 setrecursionlimit 필요.

4. 1-indexed vs 0-indexed

dp[k-1][j] + cost(j+1, mid) 에서 j 는 마지막 그룹의 시작 직전 인덱스. dp[0][0] = 0, dp[0][j>0] = INF. 이 초기화를 빼먹으면 올바른 값이 계산되지 않는다.

BOJ 연습 문제

참고

• 크누스 최적화
• Convex Hull Trick
• Aliens Trick
• 덱 트릭