Techniques In DP (2) - CHT (Convex Hull Trick)

CHT란?

Convex Hull Trick의 약자로 말 그대로 볼록껍질을 이용한 트릭이다. 

Why?

DP 문제에서 왜 사용하게 되는 트릭일까?

DP 관계식이 다음과 같이 나왔다고 생각하자.
$DP[i]=\underset{j<i}{min}(A[j]*B[i]+DP[j])$

DP[i]는 1~i까지 ~~~의 최솟값이고 이 값은 1~i-1까지의 어떤 j에 대하여 dp[j] 값과 그 이외의 값으로 관련이 있을 때 충분히 이런 형태의 식이 나올 수 있다.
이런 식을 풀어내려면 2중 for문을 돌아야 하므로 $O(N^{2})$의 시간복잡도를 가지게 된다.
하지만 우리는 이 문제를 $O(NlgN)$에 해결하고 싶고, 이때 CHT를 이용할 수 있다. 

DP식들을 일차함수꼴로 표현하여 볼록껍질을 만들어 줌으로써 해결을 한다.
A[j] = a, B[i] = x, DP[j] = b --> $ax+b$

When?

"DP식들을 일차함수꼴로 표현하여 볼록껍질을 만들어 줌으로써 해결을 한다."를 다르게 말해보면, DP식들을 일차함수 꼴로 표현했을 때 볼록껍질이 나오지 않으면 사용할 수 없는 테크닉이라는 것이다. 

볼록껍질일 조건은 맨 위의 식에서 $A[j]$의 단조성이다. 주로 최솟값을 뽑을 때에는 $A[j]$가 계속 감소하게 된다.

How?

1. 값 구하기

왼쪽과 같이 DP식에 맞는 직선들이 있을때 우리는 연속한 두 직선의 교점을 구함으로써 각 직선이 담당하고 있는 부분을 알 수 있다.
이때 담당하고 있는 부분이란 그 직선이 전체 직선중 가장 작은 함숫값을 가지게 되는 x의 범위를 뜻한다.

각 직선이 담당하고 있는 부분을 모으면 오른쪽과 같은 빨간 볼록껍질을 이룬다는 것을 알 수 있다.
직선은 순차적으로 담겨 있으므로 이분탐색을 통해 임의의 x값에 대하여 그 x값을 담당하는 직선을 $O(lgN)$만에 구할 수 있다.

만약 들어오는 x값이 순차적으로 증가한다면 전 x가 담당했던 선분 이후부터 차례대로 보면 되므로 $N$개에 대한 전체 시간복잡도를 $O(N)$에 해결할 수 있다.

따라서 볼록껍질이 잘 만들어져 있으면 최솟값은 바로 찾을 수 있다. 

2. 볼록껍질 만들기.

우리는 기본적인 조건에 의해 기울기가 순차적으로 들어온다는 것을 알고 있다. 
따라서 조금의 구간이라도 담당하고 있는 직선들을 순차적으로 모아놓으면, 인접한 두 직선의 교차점을 이용할 수 있다.

조금의 구간이라도 담당하고 있는 직선들을 관리하기 위해서 스택을 사용한다. 
제일 최근의 직선들을 보면서 조건에 맞지 않는 직선들을 빼나가는 과정을 반복하는 것이다. 
(그라함 알고리즘과 비슷한 느낌)

예를 들어 왼쪽의 그림처럼 직선집합이 있을 때, 오른쪽의 주황색과 같은 직선이 들어온다면 마지막 파란 직선은 집합에서 삭제해야 한다는 것이다. 

왼쪽 그림처럼 초록색 직선을 지워야 하는 경우는 마지막 직선을 넣을때 생기는 교점이 그 전 교점보다 x값이 작을 경우이고 그 반대의 경우에는 초록색 직선도 담당하는 구간이 있기 때문에 지우면 안된다.

이런식으로 stack에서 교차점의 x좌표를 보면서 조건에 맞지 않는동안 직선을 계속 빼나가면 된다.

코드

위에서 계속 stack이라고 했지만 사실 vector에 좀 더 가깝다. 중요한건 index에 바로 접근할 수 있는 형태여야 훨씬 더 편하다는 것이다. 그래서 c에서 구현한 stack처럼 활용을 하였다.

ll sz=0;
lin stk[1010101];
double cx(ll a,ll b) {
    return 1.0 * (double)(stk[a].b - stk[b].b) / (stk[b].a - stk[a].a);
}
void insert(lin v){
    stk[sz]=v;
    while(sz&&stk[sz].a==stk[sz-1].a&&stk[sz].b<stk[sz].b){
        stk[sz-1] = stk[sz];
        sz--;
    }
    while(1<sz&&cx(sz-2,sz-1)>cx(sz-1,sz)){
        stk[sz-1] = stk[sz];
        sz--;
    }
    sz++;
}
ll sol(ll x){
    ll lo=0,hi=sz-1;
    while(lo<hi){
        ll mid=(lo+hi)/2;
        if (cx(mid,mid+1)<=x) lo=mid+1;
        else hi=mid;
    }
    return stk[lo].a*x+stk[lo].b;
}

추천 문제

BOJ 13263 나무자르기

문제 풀기

CHT는 DP식을 전개하다가 위와 같은 형태가 나오고, 시간복잡도를 줄이고 싶을 때 사용하게 된다.
따라서 어떤 문제를 CHT임을 알고 풀기 시작하면 식을 세우는 과정에서 무조건 위와 같은 형태를 만들려고 한다.
그래서 플2~다4 사이의 DP 문제를 풀다가 자연스럽게 CHT를 써야하는 문제를 마주치는 것을 추천한다.