백준 - 사수아탕(2419)

문제

 

먼저 사탕의 개수를 최대화 하는 문제는 $k$번째 사탕을 $t_k$시간에 먹었다고 할때 $t_k$ 합을 최소화 하는 문제와 동치라는것을 알 수 있다. (문제를 좀더 쉽게 하기 위해 일단 $t_k \leqslant m$이라는 가정을 하자.)

 

그리고 나서 가장 먼저 $\text{dp}[l][r]$을 사탕의 구간 $l \sim r$ 에 대해서 $t_k$합의 최솟값으로 정의하려고 시도해 볼 수 있다. 하지만 이렇게 하면 적절한 점화식을 구할 수 없다.

 

$k$번째로 먹은 사탕을 시간 $t_k$때 먹었다고 하자. ($t_k$의 정의가 이전과 다음에 주의하자.)

우리는 최소화 하려는 대상은 $t_1 + t_2 + \cdots + t_n$ 이다. 그런데 잘 생각해보면 $t_2,t_3,\cdots,t_n$에는 모두 $t_1$이 더해져 있고, 똑같이 $t_3,t_4,\cdots,t_n$에는 $t_2$가 더해져 있다는걸 자명하게 알 수 있다.

 

방금 알아낸 사실을 이용해 다음과 같이 dp를 정의해보자.

• $\text{dp}[l][r][t]$ : 1번째부터 $(r-l+1)$번째로 먹은 사탕이 구간 $l~r$에 하나씩 있고 마지막 위치가 $t$ (t==0 ? 왼쪽 : 오른쪽) 일때 $\left[ t_1+t_2 \cdots t_{r-l+1} + t_{r-l+1} \cdot (n - (r - l + 1)) \right]$ 의 최솟값
• $\text{dp}[l][r][t] = |p_{l=r}| \cdot n \quad \text{where} \quad l = r$
• $\text{dp}[l][r][t] = \min_{t' = 0,1} \left[   \text{dp}[l'][r'][t'] + |p_i - p_{i'}| \cdot (n - (r - l))   \right]  \quad \text{where} \quad l < r $

이때 $p_k$는 정렬된 순서에서 $k$번째 사탕의 위치를 나타낸다. $i$는 $t=0$인 경우 $l$, $t=1$인 경우 $r$이다.

현재 상태가 $(l,r,t)$라면 이전 상태의 후보는 $(l',r',t')$는 $t=0$인 경우 $(l+1,r,t'=0,1)$, $t=1$인 경우 $(l,r-1,t'=0,1)$이 된다.

 

이렇게 dp를 정의하면 우리가 하고자 했던 $t_k$의 합을 전체 구간에 대해 최소화 할 수 있다.

하지만 이 dp는 어떤 $t_k$가 $m$을 초과하는 경우 즉, 최소화 하려는 대상이 $\min(t_k,m)$인 경우 답을 보장하지 못한다.$m$을 초과하는 경우에도 답을 구하기 위해서는 다음을 관찰해야 한다.

• $\sum \min(t_k,m)$를 최소화 하는 문제는 결국 $t_k>m$인 사탕들을 제외한 사탕들에 대해 $\sum t_k$를 최소화하는 문제로 바꿀 수 있다.

 

그러므로 우리는 기존에 전체 구간에 대해 $\sum t_k$ 최소화 문제를 풀었던것과 달리 모든 구간에 대해 $\sum t_k$ 최소화 문제를 풀어주면 답을 구할 수 있다.

• $\text{dp}[l][r][t]$ : 1번째부터 $(r-l+1)$번째로 먹은 사탕이 구간 $l~r$에 하나씩 있고 마지막 위치가 $t$ (t==0 ? 왼쪽 : 오른쪽) 일때 $\left[ t_1+t_2 \cdots t_{r-l+1} + t_{r-l+1} \cdot (c - (r - l + 1)) \right]$ 의 최솟값
• $\text{dp}[l][r][t] = |p_{l=r}| \cdot n \quad \text{where} \quad l = r$
• $\text{dp}[l][r][t] = \min_{t' = 0,1} \left[   \text{dp}[l'][r'][t'] + |p_i - p_{i'}| \cdot (c - (r - l))   \right]  \quad \text{where} \quad l < r $

 

단순히 기존의 $n$을 $c$로 바꾸고, $c=1,2,\cdots,n$에 대해 각각 dp를 풀어주면 된다. 총 시간복잡도는 $O(n^3)$ 이 된다.