백준 - 환상의 듀엣(11570)

문제

 

먼저 이 문제를 다음과 같은 관점으로 보자 :

문제에서 주어진 수열에서 몇개의 원소들을 선택해서 만들어진 부분수열 $a_k$와 선택하지 않은 원소들을 통해 만들어지는 부분수열 $b_k$에 대해 $(|a_1-a_2|+|a_2-a_3|+\cdots)+(|b_1-b_2|+|b_2-b_3|+\cdots)$ 의 최솟값을 구한다.

 

그리고 다음과 같이 점화식을 정의해보자.

dp[i][j] : $A_{1:i}$에 대해 i번째 원소와 임의의 원소를 선택해 수열 $a_k$를 만들고 나머지로 수열 $b_k$를 만들때 $(|a_1-a_2|+|a_2-a_3|+\cdots)+(|b_1-b_2|+|b_2-b_3|+\cdots) + |A_j-b_\text{last}|$ 의 최솟값

 

이 dp를 이용하면 다음과 같이 전체 문제에 대한 답을 구할 수 있다.

$$
\begin{equation}
\min_{k=1,2,\cdots,N-1} \text{dp}[k][k+1] + p_{k+1:N} \quad \text{where} \quad p_{a:b} = |A_a-A_{a+1}| + |A_{a+1}-A_{a+2}| + \cdots+ |A_{b-1}-A_{b}|
\end{equation}
$$

 

여기까지 따라왔으면 점화식은 어렵지 않게 구할 수 있다.

$$
\text{dp}[i][j] = \min_{k=1,2,\cdots,i} \text{dp}[k-1][k] + p_{k+1:i} + |A_j - A_{k-1}|
$$

이대로 구현해도 AC를 받을수 있지만, 점화식을 조금만 바꾸면 $O(N)$ 만에 문제를 풀수 있다. 식 (1)과 점화식을 잘 관찰하면 결국 우리는 $\text{dp}[k][k+1]$들만 필요한것을 알 수 있다.

 

최종적인 점화식은 다음과 같다 :

$$
\text{dp}[i] = \min_{k=1,2,\cdots,i} \text{dp}[k-1] + p_{k+1:i} + |A_{i+1} - A_{k-1}|
$$