[BOJ 14179] 크리스마스 이브

http://www.acmicpc.net/problem/14179

이 문제를 보면 DP로 해결할 수 있을 꼴이다. 위치 순으로 창고들을 정렬했다고 생각하고 다음과 같이 정의해보자.

$dp(i, j) := $ $i$번 창고에 마지막으로 설치했을 때 그 뒤에 $j$개를 설치하는 최소 비용

이 때 다시 그 바로 뒤에 놓을 순간이동기를 생각하면 다음과 같은 점화식이 유도된다.

$dp(n, j) = 0 $

$dp(i, 0) = \sum_{k>i} dist(i, k) w(k) $; 오른쪽에 있는 짐 모두를 $i$번으로 옮겨야 하므로

$dp(i, j) = \min_{k>i} \{ \sum_{l=i+1}^{k-1} w(l) \min(dist(i, l), dist(l, k)) + dp(k, j-1) \} $

그대로 계산하면 분명 시간 초과가 날 것이다. 빠르게 계산할 수 있는 방법을 찾아야 한다.

먼저 $j=0$일 때부터 최적화하자. $dp(i, 0)$과 $dp(i+1, 0)$의 관계에서 유도할 수 있다. $i+1$번까지 오른쪽의 모든 짐을 보냈을 때보다 $i$번까지 오른쪽의 모든 짐을 보냈을 때 오른쪽 각 짐에 대해 $w(k) dist(i, i+1)$의 비용이 더 들 것이므로,

$dp(i, 0) = dp(i+1, 0) + \sum_{k=i+1}^{n} w(k) dist(i, i+1) $

를 얻는다. $w$의 부분합을 전처리해서 각각 상수 시간에, $dp(0..n, 0)$을 선형 시간에 구할 수 있다. 문제 풀이에는 불필요하지만(위를 $O(n^2 )$) 시간에 구해도 시간 안에 답을 구할 수 있다) 문제 해결에 중요한 사고의 발판이었다.

이제 일반적인 $dp(i, j)$의 식은 각종 dp optimization이 먹힐 것 같이 생겼다. 나는 divide&conquer optimization을 이용해 풀었다. koosaga님은 convex hull optimization을 통해 풀었다. 그러기 위해서는 점화식에 자리잡고 있는 $distsum(i, k) := \sum_{l=i+1}^{k-1} w(l) \min(dist(i, l), dist(l, k))$를 전처리를 할 수 있었으면 편할 것 같다.

이제 빠르게 생각을 할 수 있을 것이다. 위 식의 특징은 중간에 어떤 $mid$ 점이 존재해, 그 왼쪽에는 $dist(i, l)$을 모두 더하고, 오른쪽에는 $dist(l, k)$를 모두 더해야 한다는 점이다. 그러면 왼쪽으로부터 차례대로 이동해가면서 구할 수 있다.

다음과 같은 기저로부터 시작해서: $distsum(i, i+1) = 0$

$distsum(i, j)$와 $mid_{ij}$가 구해져 있다면, $mid$점을 $i$보다 $k$가 더 가까워질 때까지 이동시키고 (그 사이의 점의 거리를 늘여주는 것을 잊지 말자.) 그 오른쪽의 점의 증가된 거리를 일괄적으로 $dist(j, j+1) \sum_{l=mid}^k w_l$만큼 더해준다.

위와 같이 $distsum$을 전처리하고, $O(n^2 \log n)$에 답을 구해낼 수 있다. 나는 처음에는 $i$가 고정되어 있을 때 $dp(i, j)$가 $j$에 따라 볼록한 꼴로 나타날 것이라 생각했다. 그래서 $j$가 $i$에 따라 증가함만을 보이고 슬라이딩 윈도우를 사용했으나, 반례가 있었는지 '틀렸습니다'가 떴다. 연습 때는 꽤 엄밀히 증명해보고 구현하는 것이 현명할 듯하다.