Educational Codeforces Round 133 (Div. 2) - Permutation Chain 링크
(2022.08.29 기준 Difficulty *800)
(No cheating Yes study)

문제

1부터 n까지의 정수의 수열 A이 있을 때
위치와 원소가 같은 개수를 고정성이라 하면 고정성이 낮아지도록 A의 두 원소를 교환하면서 출력

알고리즘

이 문제는 정형화된 알고리즘이 아니라 이 문제에서 제시하는 고정성이라는 수치를 임의로 낮추는 방법을 찾는 것이기 때문에, 애드혹이라고 할 수 있다.
굳이 표현을 하자면 그리디..?

풀이

처음엔 고정성이 n이다. 1부터 n까지 정렬되어 있으므로.
여기서 아무 두 원소를 교체한다. 그러면 고정성이 n - 2가 된다.
그 다음엔 교체한 두 원소 중 하나와 교체하지 않은 원소 중 하나를 교체하면 고정성이 n - 3이 된다.
이런 식으로 고정성이 0이 될 때까지 교체하여 출력하면 된다.

나는 첫번째부터 n-1번째까지의 원소를 n번째 원소와 교체하는 방식을 사용하였다.

코드

import sys; input = sys.stdin.readline

for _ in range(int(input())):
    n = int(input())
    print(n)
    arr = list(range(1, n + 1))
    print(*arr, sep = ' ') # 고정성이 n인 수열부터 출력
    for i in range(n - 1):
        arr[i], arr[-1] = arr[-1], arr[i] # 첫번째부터 마지막 전까지 마지막과 교체
        print(*arr, sep = ' ')

여담

코드포스 문제를 풀면서 느낀건데, 우리나라의 PS 사이트는 정형화된 알고리즘들을 응용하는 능력을 더욱 더 탄탄하게 만들어준다면, 코드포스는 창의성을 발휘해야 하는 애드혹 느낌의 문제가 많이 나오는 것 같다.