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]\) 중 작은 것을 골라주면 된다.