1083 소트

정말 미친듯이 틀린 문제이다..
내 acm 문제풀이 역사상  이렇게 많이 틀린 문제는 없을것이다.
그만큼 어렵다기보단 불친절한 문제라는 의미이다.
이 문제를 욕하는것은 아니고, 그것을 캐치해내지 못한 내 불찰이라고 생각한다.

각설하고 문제에 대해 설명해보자면,
숫자의 목록들이 있고, 이 숫자를 내림차순으로 정렬하려고 한다.
단, 정렬 할 땐 가장 인접한 숫자들끼리의 swap 만 가능하고, 횟수에도 제한이 있다.
이 때 정렬한 결과가 사전순으로 가장 뒷서는 경우의 숫자를 출력하는 문제이다.

여기서 사전순이라는 것이 함정인데, 실제 사전순으로 보면
9 > 10 이어야 맞다.
하지만 여기서의 사전순은 단순히 숫자의 크기를 의미한다. 즉,
10 > 9

단순한 내림차순 문제가 아니라,
숫자가 1 2 3 4 5 에 기회가 4번 이면,
답은 5 1 2 3 4 가 나와야 한다.

이 문제를 푸는 방법은 우선 현재 남은 기회로 임의의 숫자를 맨 앞으로 보낼 수 있는
범위내에서의 최댓값을 고른다.
그 최댓값을 맨앞으로 보내면서 기회를 감소시킨다.
기회가 0이 되거나 정렬이 완성될때까지 반복한다.

이 사전순이라는 의미에 낚여서 엄청 고생하고
케이스가 여러번이라는것에도 낚여서 고생했다.
보통은 케이스의 횟수를 주거나 마지막케이스를 나타내는 입력을 주는데,
이 문제엔 그것이 없어서 한번만 출력하는 문제인줄 알았다.
앞으로는 이런것에 주의해야 겠다..

소스