백준17439 꽃집

작성일 | In

문제 링크

  • http://icpc.me/17439

사용 알고리즘

  • Monotone Queue Optimization
  • Alien’s Trick

시간복잡도

  • $O(N log N log X)$

풀이

아래와 같은 O(N^2K)짜리 DP식은 쉽게 떠올릴 수 있습니다.

  • DP 정의 : D(i, j) = j번째 원소까지 i개의 구간으로 분할하는 최소 비용
  • 상태 전이 : $\displaystyle D(i, j) = min_{1 ≤ k < j}(D(i-1, k) + (j - k)\times(S_j - S_k))$
  • 시간복잡도 : $O(N^2K)$

하지만 N과 K 모두 최대 50000이기 때문에 점화식을 더 빨리 계산해야 합니다. 두 가지 DP 최적화를 사용합니다.

Alien’s Trick

ioi 2016 Aliens에서 쓰인 아이디어입니다.

K 조건을 없앤 뒤, 구간을 새로 생성할 때마다 C라는 추가 비용을 부여해봅시다.
C가 무한대로 커진다면 구간을 하나만 쓰는 것이 최적이고, C가 0이 된다면 N개의 구간으로 쪼개는 것이 최적이 될 것입니다.
DP 식은 아래와 같이 변하게 됩니다.

  • DP 정의 : $D_C(i)$ = i번째 원소까지 적절히 잘 분할했을 때의 최소비용. 단, 구간을 나눌 때마다 C만큼의 추가 비용이 들어감
  • 상태 전이 : $\displaystyle D_C(i) = min_{1 ≤ j < i}(D_C(j) + (i-j)\times(S_i-S_j) + C)$
  • 시간복잡도 : Naive $O(N^2)$

비용이 C일 때 k개의 구간을 사용하는 것이 최적이라고 한다면, k개의 구간에 대해 각각 C만큼의 추가 비용이 들어갔기 때문에 k개의 구간을 사용했을 때의 최솟값은 $D_C(n) - kC$가 됩니다.

C가 커질수록 더 적은 구간을 사용할 것이고, C가 작아질수록 더 많은 구간을 사용할 것입니다.
C를 적절히 조절한다면, K개의 구간을 사용하는 적절한 C를 찾을 수 있을 것라는 가설을 세워볼 수 있습니다.
그리고 이 가설은 참입니다. 증명은 생략합니다.

정확히 K개의 구간을 사용하도록 하는 추가비용 C는 이분탐색을 통해 구해줄 수 있습니다.

이제 $D_C(i)$를 조금 더 빠르게 계산하는 방법을 생각해봅시다.

Monotone Queue Optimization

DP 식을 정리해봅시다.

$\displaystyle D_C(n) = min(D_C(i) + (n-i)\times(S_n-S_i)+C)$
$\displaystyle D_C(n) = min(-S_in-iS_n+D_C(i)+iS_i+C)$
$\displaystyle D_C(n) = min(S_in+D_C(i)+iS_i-iS_n)+nS_n+C$

3번째 줄에서 $iS_n$만 없으면 CHT를 돌릴 수 있을텐데, 아쉽게도 그러지는 못합니다.
대신 2번째 줄에서 n과 S_n을 각각 x, y로 치환하면 ax+by+c 혹은 ax+bS_x+c꼴의 식이 나오는 것을 볼 수 있습니다. 이 식을 잘 갖고 놀아봅시다.

$f_i(x) = -S_ix-iS_x+D_C(i)+iS_i+C$라고 정의합시다.
i < j일 때 $f_i(x)$와 $f_j(x)$는 어떤 점 cross(i, j) 이전에서는 $f_i(x)$가 더 작고, cross(i, j) 이후에서는 $f_j(x)$가 더 작습니다. 다시 말해 교점이 하나입니다.

$f_i(x)$가 직선은 아니지만 교점이 하나만 존재하므로 직선에서의 CHT와 비슷한 풀이를 생각해볼 수 있습니다.

$D_C(i) = min(D_C(j)+cost)$를 계산할 때 구간 [i, n]에 있는 원소들에 대해서 답이 될 수 있는 후보 j들을 큐 Q에 순서대로 넣어줍시다. Q에는 답이 될 수 있는 j들만 넣었기 때문에 cross($Q_i, Q_{i+1}$) < cross($Q_{i+1}, Q_{i+2}$)를 만족합니다.

최솟값을 구할 때는 cross($Q_1, Q_2$) < i일 때까지 계속 pop을 해주면 되고, 새로운 j를 삽입할 때는 CHT와 비슷한 느낌으로 맨 뒤에 있는 원소 두 개와 새로운 원소를 비교해 pop과 push를 적절히 해주면 됩니다.

cross(i, j)는 $O(log N)$에 구할 수 있고, cross(i, j)를 $O(N)$번 호출하기 때문에 점화식을 $O(N log N)$에 계산할 수 있습니다.
혹은 교점이 하나라는 점을 이용해 Li-Chao Tree를 이용해 $O(N log N)$에 구할 수도 있습니다.

결국 추가 비용 C를 고정시켰을 때 $O(N log N)$만에 DP식을 계산하고, C는 이분탐색을 이용해 $O(log X)$ 스텝만에 찾을 수 있으므로 $O(N log N log X)$에 문제를 풀 수 있습니다.