[백준] 26599 용 조련사 룰루

26599번: 용 조련사 룰루

풀이 아이디어

 

각각의 용이 장소내에 다른 모든 용에 대하여 m보다 크지 않도록 하여 다른 장소로 옮기는 문제이다.

 

이 문제의 풀이법은 애드혹으로 문제를 푸는 핵심 포인트는

시작장소와 도착장소에 서로를 억제할 수 있는 가장 큰 두 쌍의 용을 두는 것이 중요하다.

 

1, 2번째로 큰 용을 한 쌍, 3, 4번째로 큰 용을 한 쌍으로 묶는다.

 

1, 2번 째 용을 옮긴다음

3, 4번째 용을 제외한 모든 용을 옮기고 나서 

남아있던 3, 4번째 용을 옮기면 된다.

 

주의할 점은 위 4마리의 용들은 인접한 용들간의 차이가 m이하 여야 된다.

그렇지 않다면, 용을 옮기는 과정에서 학살이 일어나게 된다.

 

따라서 4마리 이상이 주어진다면, 정렬 후 1~4번째 큰 용들의 차이가 m이하로 연속적인지 판단 후

그 여부에 따라 위 방식으로 출력하면 된다.

 

3마리만 주어진다면

3마리가 m이하로 연속적인지 아닌지 판단하고

3마리가 연속적이라면 용을 오름차순으로 출력하면된다.

 

2마리나 1마리는 무조건 가능하니 순서만 출력하면 된다.

 

시행착오

 

아이디어가 금방 떠올라서 비교적 쉽게 풀었다.

 

3마리일 때 연속적이라면 1 2 3을 출력하게 했는데

이게 아니라 가장 큰 순서대로 출력해야 했다.

 

 

최적화 하기

O(log N * N) 이 걸리는 풀이법인데

정렬을 하지 않고 푸는 방법은 아마 없을 것 같다.