수(기타) 놀이터

|

문제 코너

|

제출 현황

|

수학 Q/A

|

수학 quiz

|

koi_monkey 대회 풀이

이 문제는 모든 원숭이에 대해 앙숙관계가 최대 3개 이하라는 점을 이용하여 해결할 수 있다. 주어진 관계를 그래프로 나타내어 보면 각 원숭이를 정점으로 앙숙관계를 양방향 간선으로 표현할 수 있는데 이 때 각 정점의 차수는 3 이하가 된다.

 먼저 원숭이들을 아무렇게나 두 개의 우리로 분할하고, 같은 우리 내에 있는 앙숙관계의 수를 라고 하자. 이제, 조건에 맞지 않는 원숭이를 아무거나 하나 고르고 이것을 반대편으로 옮긴다. 여기서 조건에 맞지 않는다는 것은 같은 우리 내에 앙숙인 원숭이가 2마리나 3마리 있다는 뜻이므로 반대편에는 무조건 0마리 또는 1마리의 앙숙인 원숭이가 있을 것이다. 따라서 이 원숭이를 반대편으로 옮기면 이 원숭이는 더 이상 조건을 위배하지 않는다.

 이 작업을 계속 반복하면 한 번 이러한 작업을 할 때마다 조건을 위배하는 원숭이를 하나 이상 없앨 수 있고 이를 모든 원숭이가 조건을 만족할 때 까지 할 수 있기 때문에 항상 해를 구할 수 있다.

 앙숙관계는 최대 개 있을 수 있고, 한 번 이 작업을 할 때마다 적어도 앙숙관계가 하나 이상 줄어듦으로 많아야  회의 작업을 거치면 어떤 원숭이도 조건을 위배하지 않게 된다. 

따라서  의 시간 복잡도로 해결할 수 있다.