수정 예정
점화식 조건
Convex Hull Trick(CHT, Convex Hull Optimization)은 아래 조건을 만족할 때 사용 가능합니다.
dp[i] = min(dp[j] + b[j] * a[i]), j < ib[j] >= b[j+1]
위 조건을 만족하면 O(n2)을 O(n log n)으로 줄일 수 있습니다. 추가로 a[i] <= a[i+1]을 만족하면 O(n)까지 줄일 수 있습니다.
이 글에서는 O(n) CHT만 다룹니다.
해결 방법
dp[i] = min(dp[j] + b[j] * a[i])에서 a[i]를 x로 잡읍시다.
그러면 이 식은 f(x) = b[j] * x + dp[j] 꼴의 일차함수로 바뀌게 됩니다. 이때 쿼리는 x좌표가 주어졌을 때 여러 f(x) 중 최솟값을 구하는 쿼리가 들어옵니다.
이렇게 4개의 일차함수가 있다고 합시다. 이 때 최솟값이 존재하는 위치는 아래와 같습니다.
최솟값이 존재하는 위치의 형태가 Convex Hull 모양이기 때문에 Convex Hull Trick이라 부릅니다.
일차 함수를 추가할 때는 이진 탐색을 이용하여 O(log n)만에 수행할 수 있습니다만, a[i] <= a[i+1] 조건을 만족하면 i가 증가함에 따라 x = a[i]도 증가하기 때문에 스택을 이용하여 스위핑을 하면 amortized O(1)에 수행할 수 있습니다.
빨간색(1번)과 노란색(2번) 함수가 있는 상황에서 초록색(3번) 함수를 넣는다고 가정해봅시다.
1번과 2번의 교점이 2번과 3번의 교점보다 왼쪽에 있다는것은 2번 함수가 쓸모 있다는 것을 의미합니다.
이 그림에서는 1번과 2번의 교점이 2번과 3번의 교점보다 오른쪽에 있습니다. 이것은 2번 함수가 전혀 쓸모가 없다는 것을 의미합니다. 그러므로 2번 함수를 제거해주고 3번 함수를 넣어주면 됩니다.
위와 같이 스택을 이용하면서 스위핑을 해주면 n개의 함수를 처리할 때 O(n)만에 처리를 해줄 수 있습니다.
코드는 (여기)에서 볼 수 있습니다.