분할 정복을 이용한 최적화

이 글은 시리즈의 일부입니다. 먼저 이전 글을 모두 읽기를 권장합니다.

기본 풀이의 DP 갱신 공식을 살펴봅시다:

주어진 상태에 대한 최적의 $k$를 $opt[i, j]$로 나타냅시다. 즉, 위 식의 argmin입니다. 최적 인덱스가 하나가 아닌 경우, 명확성을 위해 그중 가장 오른쪽 인덱스를 선택합니다.

구체적으로 점을 구간으로 덮는 문제에서는 다음과 같은 점을 알 수 있습니다:

직관은 다음과 같습니다: 더 긴 점들의 접두사를 덮어야 한다면, 마지막 선분의 시작점은 결코 더 앞쪽에 오지 않습니다.

#알고리즘

$opt[l, k]$와 $opt[r, k]$를 이미 알고 있고, $l$과 $r$ 사이의 어떤 $i$에 대해 $opt[i, k]$를 계산하려 한다고 합시다. 그러면 위의 부등식을 이용하여 $i$에 대한 최적 인덱스를 탐색하는 구간을 전체 구간 $[0, i - 1]$에서 $[opt[l, k], opt[r, k]]$로 좁힐 수 있습니다.

다음과 같이 합시다. $k$번째 층에서 구간 $[l, r]$에 대한 DP 값을 계산하는 재귀 함수를 만드는데, 이때 그 값들의 $opt$가 $l’$과 $r’$ 사이에 있다는 것을 알고 있다고 합니다. 이 함수는 단순히 구간 $[l, r]$의 중앙을 잡아 선형 탐색으로 그 지점의 답을 계산한 다음, 두 절반에 대해 각각 $[l’, opt]$와 $[opt, r’]$를 경계로 넘겨 재귀적으로 호출됩니다.

// [ l,  r] -- какие динамики на k-том слое посчитать
// [_l, _r] -- где могут быть их ответы
void solve(int l, int r, int _l, int _r, int k) {
    if (l > r)
        return; // отрезок пустой -- выходим
    int opt = _l, t = (l + r) / 2;
    // считаем ответ для f[t][k]
    for (int i = _l; i <= min(_r, t); i++) { 
        int val = f[i + 1][k - 1] + cost(i, t - 1);
        if (val < f[t][k])
            f[t][k] = val, opt = i;
    }
    solve(l,     t - 1, _l,  opt, k);
    solve(t + 1, r,     opt, _r,  k);
}

그런 다음 각 층에 대해 이 함수를 차례로 호출합니다:

for (int k = 1; k <= m; k++)
    solve(0, n - 1, 0, n - 1, k);

구간 $[l, r]$는 호출할 때마다 대략 절반으로 줄어들므로, 재귀 깊이는 $O(\log n)$입니다. 한 «레벨»에 있는 모든 원소의 탐색 구간은 기껏해야 경계에서만 겹칠 수 있으므로, 각 레벨에서 탐색이 확인하는 서로 다른 인덱스는 모두 합해 $O(n)$개입니다. 따라서 한 레이어 전체를 다시 계산하는 데에는 기본 풀이의 $O(n^2)$ 대신 $O(n \log n)$번의 연산이 듭니다.

따라서 점근적 복잡도를 $O(n \cdot m \cdot \log n)$으로 개선했습니다.