[BOJ 12825] Next Permutation

문제: https://www.acmicpc.net/problem/12825

 

힌트 1:

$3-1-2$ free permutation과, (모든 $i$에 대해) "$A_1, \cdots, A_i$의 maximum을 $v$라고 했을 때, 이후 등장하는 $A_{i+1}, \cdots, A_N$ 에 등장하는 $v$ 미만의 수만 모으면 모두 내림차순으로 등장해야 한다"는 말은 동치입니다.

 

힌트 2:

임의의 수열에 관한 Next Permutation은 어떻게 구현할까요? https://en.cppreference.com/w/cpp/algorithm/next_permutation 를 참고합시다.

 

풀이:

"힌트 1"의 관찰을 사용하면, $A_1, \cdots, A_i$가 3-1-2 free permutation일 때, 남은 수 들을 내림차순으로 전부다 붙여도 3-1-2 free permutation입니다. 그렇기 때문에 $A_j, \cdots, A_N$이 내림차순이 되지 않도록하는 처음 인덱스 $j$를 찾으면, 해당 위치의 수부터 바꾸어줘야 합니다. $A$의 다음 수열을 $B$라고 하면, $A_1, \cdots, A_{j-1} = B_1, \cdots B_{j-1}$이 됩니다.

 

이제, $B_j$를 찾아줍시다. $B_j$는 $A_{j+1}, \cdots, A_N$ 중 $A_j$ 보다 큰 가장 작은 수여도 괜찮습니다. 이는, 주어진 3-1-2 free permutation에 대해 가장 마지막 수를 증가시켜도 3-1-2 free permutation이 되기 때문입니다.

 

이제, 나머지 수를 배치해봅시다. $B_{j+1}$에 올 수 있는 수는 이제까지 등장하지 않은 수 중 $\max(B_1, \cdots, B_j)$ 초과의 아무 수나, $\max(B_1, \cdots, B_j)$ 미만 수의 최댓값입니다. (힌트 1의 관찰에 따라, 해당 수들은 내림차순으로 배치되어야 하기 때문입니다.)

즉, 나머지 수 중 $\max(B_1, \cdots, B_j)$ 미만의 수를 내림차순으로 배치해주고, 나머지 수를 오름차순으로 배치해주면 사전순으로 최솟값이 됩니다.

 

코드: https://www.acmicpc.net/source/share/179ee49d77f244b78cd98ffe286d9729