Convex Hull Trick

DP 테이블의 각 값을 계산하는데, DP 테이블(또는 다른 배열)의 연속된 값들의 단순 연산 값이 필요하다면 누적합이나 Segment Tree등을 이용해 최적화 할 수 있다는 말을 전 글에서 설명한 바 있습니다.

 

https://anz1217.tistory.com/130

기초 DP 최적화

 

하지만 더 복잡한 수식을 계산한 값이 필요하다면 어떻게 해야 할까요?

DP를 최적화하는 방법 중 하나인 Convex Hull Trick에 대해 알아봅시다.

 

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

\(DP_i = \min_{j < i}(DP_j + A_i \cdot B_j)\) (\(B_j\)는 \(j\)가 증가함에 따라 감소)

 

그러면 \(DP_i\)를 구할 때 \(A_i\)는 고정된 값이므로, \(B_j\)의 값과 \(DP_j\)의 값에 집중해 봅시다.

\(A_i\)를 \(x\)로 치환한 다음, \(y = B_j \cdot x + DP_j\)라는 직선의 그래프를 모두 그려보면 대충 다음과 같은 형태가 됩니다.

 

 

우리는 최소값만이 필요하므로, 우리는 각 직선에 대해 오른쪽 그림에서 빨간색 선으로 표시한 부분만 필요합니다.

각 직선을 사용하게 되는 \(x\)의 범위를 저장하면, \(A_i\)의 값에 따라 어떤 직선을 사용해야 하는지 이분탐색을 이용해 구할 수 있게 됩니다.

 

시간복잡도는 \(O(n\log n)\)입니다.

 

빨간색 선으로 이루어진 부분이 볼록 껍질과 비슷한 형태를 이룹니다. 이 최적화의 이름이 Convex Hull Trick인 이유입니다.

 

 

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

13263번: 나무 자르기

 

아무튼 \(n\)번째 나무만 자르고 나면, 그 이후는 필요한 충전 비용이 0이므로 남은 나무들을 다 잘라버릴 수 있습니다.

 

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

\(DP_i :\) 마지막으로 자른 나무가 \(i\)번 나무일 때 사용한 충전 비용의 최소값

\(DP_i = \min_{j<i}(DP_j + a_i \cdot b_j)\)

 

\(b_j\)는 \(j\)가 증가함에 따라 감소하므로, 위에서 설명한 형태와 동일합니다. Convex Hull Trick을 사용할 수 있습니다.

 

#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; }
 
int n;
ll a[100001];
ll b[100001];
ll dp[100001];
 
struct Line
{
    ll a, b; // a*x+b
    double start = 0.0; // 이 직선을 사용하기 시작하는 x좌표값
    bool operator<(Line l) const { return start < l.start; }
};
 
vector <Line> lv;
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
 
    lv.push_back({ b[1],0,0.0 });
 
    for (int i = 2; i <= n; i++)
    {
        Line tmp = { 0,0,a[i] };
        Line res = *prev(upper_bound(lv.begin(), lv.end(), tmp));
        // 이분탐색으로 필요한 직선을 찾음
        
        dp[i] = res.a * a[i] + res.b;
 
        Line nxt = { b[i], dp[i], 0.0 };
        while (true)
        {
            Line prv = lv.back();
            double cross = (double)(prv.b - nxt.b) / (nxt.a - prv.a);
            // 새로 넣으려는 직선과(nxt) 현재 가장 뒤에 있는 직선(prv) 과의 교점
 
            if (cross <= prv.start)
            {
                // prv 시작점보다 교점의 x좌표가 작으면, prv는 필요없는 직선이다.
                lv.pop_back();
                continue;
            }
 
            nxt.start = cross;
            lv.push_back(nxt);
            break;
        }
    }
 
    cout << dp[n];
}

---

특수한 경우

만약 \(A_i\)가 \(i\)가 증가함에 따라 역시 증가한다면, 굳이 모든 직선을 가지고 있을 필요가 없습니다. 앞에 필요없어진 직선은 그냥 버리면 되기 때문입니다.

 

따라서 이 경우 \(O(n)\)에 구현할 수 있게 됩니다.

 

#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; }
 
int n;
ll a[100001];
ll b[100001];
ll dp[100001];
 
struct Line
{
    ll a, b; // a*x+b
    double start = 0.0; // 이 직선을 사용하기 시작하는 x좌표값
    bool operator<(Line l) const { return start < l.start; }
};
 
deque <Line> lv;
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
 
    lv.push_back({ b[1],0,0.0 });
 
    for (int i = 2; i <= n; i++)
    {
        Line tmp = { 0,0,a[i] };
        while (lv.size() > 1 && lv[1].start <= a[i]) lv.pop_front();
 
        Line res = lv.front();
    
        dp[i] = res.a * a[i] + res.b;
 
        Line nxt = { b[i], dp[i], 0.0 };
        while (true)
        {
            Line prv = lv.back();
            double cross = (double)(prv.b - nxt.b) / (nxt.a - prv.a);
            // 새로 넣으려는 직선과(nxt) 현재 가장 뒤에 있는 직선(prv) 과의 교점
 
            if (cross <= prv.start)
            {
                // prv 시작점보다 교점의 x좌표가 작으면, prv는 필요없는 직선이다.
                lv.pop_back();
                continue;
            }
 
            nxt.start = cross;
            lv.push_back(nxt);
            break;
        }
    }
 
    cout << dp[n];
}

 

일반적인 경우

지금까지는 \(B_j\)는 \(j\)가 증가함에 따라 감소한다는 조건이 붙었는데, 이러한 조건이 없어도 최적화 할 수 있습니다.

각 직선을 STL set등의 BBST로 관리해 주면서 직선의 중간 삽입을 구현할 수도 있고, 또는 Li-Chao Tree라는 자료구조를 이용하면 됩니다.

---

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

 

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

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

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

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

ANZ1217