BOJ 1906 자리 바꾸기

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

O(NlogN K!) 시간 초과 풀이

최종적으로 만들어야 하는 수열은 K!개 중 하나입니다. 그중 하나를 고정했을 때, 몇 번의 자리 교체가 필요할까요?

만약 순열을 오름차순으로 정렬해야 할 경우, 답은 반전의 개수와 같음이 알려져 있습니다. 이를 구하려면:

• 먼저 빈 공간을 N개 만듭니다.
• 주어진 순열에서 1의 위치를 찾아, 거기에 1을 넣습니다. 이때 반전의 개수는 "1의 왼쪽에 있는 빈 공간 개수"만큼 추가됩니다. 예를 들어 순열이 ? ? ? ? 1 ? 꼴이면 4가 추가됩니다.
• 그 다음으로 2를 넣고, 2의 왼쪽에 있는 빈 공간 개수만큼 반전의 개수가 추가됩니다. 예를 들어 순열이 ? ? ? ? 1 2 꼴이면 4가 추가됩니다.

이 과정을 이 문제에 적용해 봅시다. 맨 처음에 와야 하는 그룹을 왼쪽에서부터 차례대로 집어넣고, 넣을 때마다 반전의 개수를 갱신합니다. 예를 들어 예제 입력 2 2 3 2 1 3 1이 주어지고, 맨 처음에 그룹 3이 와야 한다면, 첫 번째 3을 넣어 반전이 2개, 두 번째 3을 넣어 반전이 4개 추가됩니다. 이를 최종 수열의 순서대로 진행하면 됩니다. 왼쪽에서부터 차례대로 집어넣어야 하는 이유는 그래야 반전의 개수가 최소가 되기 때문입니다.

이 과정은 펜윅 트리로 O(NlogN)에 구현할 수 있지만 그러면 당연히 시간 초과가 납니다.

O(NK K!) 시간 초과 풀이

한 그룹의 사람들은 왼쪽에서부터 차례대로 집어넣기 때문에,