백준 23354 - 돌 가져가기

https://www.acmicpc.net/problem/22354

 

해당 포스트에서는 공식 풀이에서 명확하지 않을 수 있는 부분에 부연 설명을 달았다. 먼저 보고 오도록 하자.

x 양 옆 중 하나는 최적해가 아니라고?

아마 풀이에서 가장 이해가 되지 않는 부분일 수 있다. 얼핏 생각하면 저 하이라이트 한 부분에서는 다음과 같은 경우에 의해 반례가 있을 수도 있다는 생각을 할 수 있다.

 

WBWBWBWBW

1 5 5 5 1 1 1 1 1

 

이는 최적으로 가져가야 할 돌들이 한 곳에 뭉친 경우이다. 여기서 세 번째 돌을 취하려 하면 두 번째나 네 번째 돌을 버리란 말이냐!? 와 같은 의구심이 생길 수 있다.

끝부터 가져가자

조금만 더 생각하면 답은 의외로 쉽다. 가장 끝부분인 4번째 돌부터 내부로 향하면 된다.

 

그러면 위 그림처럼 가져갈 돌과 버릴 돌을 짝지을 수 있게 되고 공식 풀이에서 언급한 $\frac{N}{2}$ 개의 최적 행동을 실현할 수 있게 된다.

 

최적 돌들이 sparse 하게 퍼진 경우에는 양 옆 중 하나가 최적의 돌이 아닌 경우가 있을 것이 자명하므로 간단하게 처리할 수 있다.