Divide and Conquer Optimization

DP를 최적화 하는 방법 중 하나인 Divide and Conquer Optimization에 대해 알아봅시다.

 

DnC Optimization은 DP점화식이 다음과 같은 형태일 때 사용할 수 있습니다.

1. \(DP_{i, j} = \min_{k < j}(DP_{i-1, k} + C_{k, j})\)

2. \(A_{i, j}\)가 위 식에서 \(DP_{i, j}\)가 최소값이 되기 위한 최소 \(k\)라고 했을 때, \(A_{i, j} \le A_{i, j+1}\)

 

풀어서 얘기하면, \(DP_{i, j}\)가 최소가 되는 \(k\)를 \(x\)라고 하고, \(DP_{i, j+1}\)가 최소가 되는 \(k\)를 \(y\)라고 했을 때, \(x \le y\)일 때 사용할 수 있습니다.

 

그래서 어떻게 최적화 할 수 있을까요?

\([l, r]\)범위에 있는 \(j\)에 대해, 모든 \(DP_{i, j}\)값을 구한다고 생각해봅시다.

이 때, 가능한 \(k\)의 범위는 \([s, e]\)라고 가정합니다.

 

먼저 범위 \([l, r]\)의 중간에 있는 수 \(m = \lfloor \frac{l+r}{2} \rfloor \)에 대해, \(DP_{i, m}\)을 Naive하게 구해줍니다.

이 때 DP값이 최소가 되는 최소 \(k\)를 \(A_{i, m}\)이라고 합시다.

 

그러면 \(m\)을 기준으로 왼쪽에 있는 DP값들은 \(j\)의 범위가 \([l, m-1]\), \(k\)의 범위가 \([s, A_{i, m}]\)가 되고,

오른쪽에 있는 DP값들은 \(j\)의 범위가 \([m+1, r]\), \(k\)의 범위가 \([A_{i, m}, e]\)가 됩니다.

일단 이를 재귀로 구현할 수 있다는 사실을 알 수 있습니다.

 

시간복잡도는 어떻게 될까요?

\(j\)의 범위는 한 단계마다 절반으로 줄어들게 됩니다. 각 단계마다 Naive하게 계산해야 하는 경우의 수의 합은 초기 범위 \([s, e]\)의 크기에 비례합니다.

따라서 하나의 \(i\)값에 대해, \(j\)의 범위와 \(k\)의 범위의 크기가 \(n\)으로 동일하다면 \(O(n\log n)\)의 시간복잡도를 가지게 됩니다.

 

DnC Optimization을 이용하기 위해서는 상기한 2개의 조건을 만족해야 합니다. 1번 조건의 경우 점화식으로 해당 형태가 나타나는지 쉽게 알 수 있지만, 2번 조건은 직관적으로 알기 힘든 경우가 많습니다.

이를 배열 \(C\)가 Monge array인지 확인함으로써, 이를 만족하는지 쉽게 알 수 있습니다.

임의의 \(a \le b \le c \le d\)에 대해, \(C_{a, c} + C_{b, d} \le C_{a, d} + C_{b, c}\)를 만족한다면, 배열 \(C\)는 Monge array이며, 위의 2번 조건을 항상 만족합니다.

단, \(C\)가 Monge array라는 사실과 2번 조건이 필요충분조건은 아니라는 사실에 주의합시다.

 

 

https://www.acmicpc.net/problem/13261

13261번: 탈옥

 

DP를 다음과 같이 정의합시다.

\(DP_{i, j} : \) \(i\)명의 간수가 1번 칸부터 \(j\)번 칸까지의 감옥을 감시할 때, 탈옥 위험도의 최소값

\(DP_{i, j} = \min_{k < j}(DP_{i-1, k} + sum_{k+1, j} \cdot (j - k)))\) (\(sum_{l, r} :\) \(l\)번 칸부터 \(r\)번 칸 까지 수감되어있는 죄수들의 탈옥력의 합)

 

점화식의 형태가 1번을 만족하고, \(C\) 배열이 Monge array이므로 DnC Optimization을 사용할 수 있습니다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
ll n, k;
ll psum[8001];
ll dp[801][8001];
 
void solve(int i, int l, int r, int s, int e)
{
    if (l > r) return;
 
    int m = (l + r) / 2;
    ll ans = 1e18;
    int opt = -1;
 
    // Naive
    for (int j = s; j <= min(e, m - 1); j++)
    {
        ll res = dp[i - 1][j] + (psum[m] - psum[j]) * (m - j);
        if (ans > res)
        {
            ans = res;
            opt = j;
        }
    }
 
    dp[i][m] = ans;
 
    solve(i, l, m - 1, s, opt);
    solve(i, m + 1, r, opt, e);
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n >> k; k = min(k, n);
    for (int i = 1; i <= n; i++)
    {
        cin >> psum[i];
        psum[i] += psum[i - 1];
    }
 
    for (int j = 1; j <= n; j++)
        dp[1][j] = psum[j] * j; // 기저사례
 
    for (int i = 2; i <= k; i++)
    {
        solve(i, i, n, i - 1, n - 1);
    }
 
    cout << dp[k][n];
}

---

제 그룹의 문제집에서 연습 문제들을 관리하고 있습니다.
문제집의 문제들을 보고 싶으시다면, 가입 신청을 해 주세요.

 

+ 요즘 많이 가입 신청이 들어오고 있습니다만, 꼭 그룹에 가입하셔서 제 문제들을 푸실 필요는 없습니다.

solved.ac 에서 태그를 찾아 푸시거나 백준 단계별로 풀기 에서 문제를 찾아 푸셔도 충분합니다!

그룹은 단순히 제 개인용 알고리즘 문제집 정리 용도이니 참고해주세요!

https://www.acmicpc.net/group/7712

ANZ1217