BOJ 17439 꽃집

꽃들의 가격이 v[1], v[2], ..., v[N]까지 있을때, 이를 최대 K개의 구간으로 분할하여 각 구간에 대한 (구간에 있는 꽃의 개수)*(꽃들의 가격의 합)의 합을 최소화하라는 문제이다. 각 꽃은 정확히 하나의 구간에 포함되어야 하고, 임의의 1≤i<N에 대해 v[i]≤v[i+1]을 만족한다.

 

일단 첫번째로 알아내야 하는 것은 최적의 분할은 K개의 구간으로 나눌때 생긴다는 사실이다. i개의 구간으로 나누었을때의 최적해에서 어느 구간 하나를 두개의 구간으로 분리하면 최종 값이 줄어든다는 사실을 이용해 이를 귀납적으로 보일 수 있다.

 

또 하나 관찰해야 할 사실은 i개의 구간으로 나눴을때의 최적해를 D[i]라 하면, D[i-1]-D[i]≥D[i]-D[i+1]로, (i, D[i])를 평면상에 찍었을 때 찍은 점들이 convex한 모양을 이룬다는 것이다. 자세한 증명은 생략한다.

 

따라서 우리는 Alien Trick을 적용하여 문제를 풀 수 있는 여지가 생겼다. 이제, 구간을 하나 새로 생성하는데 부여되는 가중치를 x라 두고 DP 점화식을 세워보자.

 

DP[i]를 1~i까지 고려했을 때의 최적해라 생각하면, DP[i]=min(DP[j]+(i-j)*(sum[i]-sum[j]))+x를 만족한다. (j<i) 이때 sum은 v의 누적합 배열이다.

 

안타깝게도 위의 점화식은 잘 알려진 CHT와 같은 방법으로 푸는 것이 까다로운 꼴이다. 그러나, C[j][i]=(i-j)*(sum[i]-sum[j])라 했을 때 C는 Monge Array의 조건을 만족하므로, Monotone Queue Optimization을 활용하여 해결할 수가 있고, 이에 대한 설명은 구사과님의 블로그에 잘 나와있다.