BOJ 22907 - 오렌지 키우기

랜덤 플레 디펜스를 하다 풀게 된 문제이다. 오렌지 컵 문제인데, 에디토리얼도 아직 없고 구글링했을 때 풀이가 나오지 않길래 내가 적어보려 한다. 앞으로도 푼 백준 문제들 중에 자료가 없는 것들은 이렇게 풀이를 작성할 예정이다.

 

문제 요약

오렌지 농장에 $N$개의 오렌지를 심을 수 있는 지점이 있다. 오렌지는 심은 후 $k$초가 지나면 수확이 가능하다. 모든 지점에 오렌지를 심고 모든 지점에서 오렌지를 수확하기 위한 최소의 시간을 구하여라.

 

풀이

$DP[i]$를 $i$번째 오렌지까지 모두 수확하고 i번째 지점에서 멈췄을 때의 최소 시간으로 정의하자. 그러면 다음과 같은 점화식을 통해 $DP[i]$를 구할 수 있다:

$DP[i]=min_{0<=j<i}(DP[j]+ar[i]-ar[j]+max(2(ar[i]-ar[j+1]),k) )$

이 점화식이 나타내는 상황은 $j$번째 오렌지까지 모두 수확한 상태에서, $j+1$번째 오렌지부터 $i$번째 오렌지까지 차례대로 심은 후, $j+1$번째 오렌지로 돌아간 후 다시 순서대로 수확하는 상황이다. 이 상태로는 $O(N^2)$보다 빠르게 구하는 것이 불가능한 것처럼 보인다. 그 이유는 DP식 안의 max 때문이니, 이를 지우기 위해 경우를 나누어 보자.

 

$DP[i]=min(DP[j]-ar[j]-ar[j+1]+3ar[i]), (2(ar[i]-ar[j+1])>=k)$

$DP[i]=min(DP[j]-ar[j]+ar[i]+k), (2(ar[i]-ar[j+1])<k)$

 

이 때, 각 경우에 해당하는 $j$는 연속된 구간으로 표현된다. 즉, 어떤 위치 $j_0$를 기준으로 그 이전은 전자, 이후는 후자의 경우가 되는 $j_0$가 존재한다는 뜻이다. 또한, 이 $j_0$는 $i$가 증가함에 따라 증가한다. 따라서, 이 $j$를 투 포인터처럼 관리할 수 있다. (혹은 이분 탐색을 사용할 수도 있다.) 

 

이를 처리하고 나면 각 경우의 DP식을 $DP[j]-ar[j]-ar[j+1]$, $DP[j]-ar[j]$를 저장하는 최솟값 세그먼트 트리 등으로 구할 수 있다. 여기까지 마치면 $DP[n]$이 답인 것 같지만, 그렇지 않다.

 

마무리는 반드시 $n$번째 지점에서 할 필요가 없기 때문이다. 예제 2번이 이 경우에 해당한다. 즉, 각 $i$에 대해 $i$번째 지점까지 수확을 완료한 후 $n$번째 지점까지 갔다가, 수확을 기다린 후 다시 $i+1$번째 지점까지 돌아오는 경우를 고려해주어야 한다. 따라서, 최종 답은 $min(DP[i]+ar[n]-ar[i]+k+ar[n]-ar[i+1])$과 $DP[n]$ 중 작은 것을 골라주면 된다.