BOJ 2516 : 원숭이
https://www.acmicpc.net/problem/2516 2516번: 원숭이 첫째 줄에는 원숭이들의 수를 나타내는 하나의 정수 N이 주어진다. 단, N은 3이상 100,000이하의 정수이다. 둘째 줄부터 N개의 줄에는 1번부터 번호순서대로 각 원숭이에 대해 앙숙관계에 있는 원숭 www.acmicpc.net 신기한 그리디 문제다. 모든 원숭이를 한 우리에 모아두고 앙숙관계가 2마리 이상인 원숭이들을 다른 곳으로 옮겨놓는 방식으로하면 된다. i) 옮길 원숭이가 없다면 모든 원숭이에 대해 같은 우리에 앙숙관계인 원숭이가 1마리 이하임을 의미하므로 문제의 답을 찾을 수 있다. ii) 옮기는 경우가 있다면 옮기고 나서 앙숙관계인 원숭이가 1개 이상 줄어든다. 그러므로 이런 상황은 통틀어서 총 3n번까지 ..
2021.08.06