BOJ 2516 : 원숭이

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

2516번: 원숭이

신기한 그리디 문제다. 

모든 원숭이를 한 우리에 모아두고 앙숙관계가 2마리 이상인 원숭이들을 다른 곳으로 옮겨놓는 방식으로하면 된다.

 

 

<증명>

 

i) 옮길 원숭이가 없다면 모든 원숭이에 대해

같은 우리에 앙숙관계인 원숭이가 1마리 이하임을 의미하므로 문제의 답을 찾을 수 있다.

 

ii) 옮기는 경우가 있다면 옮기고 나서 앙숙관계인 원숭이가 1개 이상 줄어든다.

그러므로 이런 상황은 통틀어서 총 3n번까지 가능하다.

 

 

 

그러므로 시복은 O(n).

코드