2026-02-25 문제풀이

35308 PPPP

잡설

음.. 문제 이해를 똑바로 좀 하자… 오늘은 간단한 문제 하나만 풀고 쉬려다가 출력초과땜에 스트레스 좀 받았다 ㅎㅎ

풀이

사이클의 크기가 N인 순열 사이클을 만들어야한다.

• $P_{1} = K$
• $P_{K} = x$
• $P_{x} = x_2$

뭐 이런식으로 뻗어나갈텐데 편하게 배열을 하나 만들어보니

$K=7$ 일 때, 위 처럼 편하게 구할 수 있었다.
그러니까 K, K+1, K+2 .. 2, 3, .. K-1 1 순으로 넣으면 된다.
…고 생각했다.

근데 이 생각은 완전히 틀렸다.

위 그림에서

• $P_{1} = K = 7$ 은 성립한다.
• $P_{2}=P_{P_{1}}=P_{K}$ 이다. 여기서 각 요소는 한번씩 사용되므로 $K=2$라는 결과가 나온다. 따라서 $K=2$ 일때만 사이클을 순차적으로 만들 수 있다는 것이다.

나는 그냥 $P_2$ 를 정해준걸 개무시하고 풀고 있었던 것이다. 뭐한거지?

따라서 알고리즘은 다음과 같다.

1. $N = 1$이면 $K=1$이다. 따라서 1출력
2. $K\ne2$ 이면 -1 출력
3. 나머지 경우는 2, 3, … n, 1을 출력하면 된다.

코드

import sys
input = sys.stdin.readline
for _ in range(int(input())) : 
    N, K = map(int, input().split())
    if N == 1 :
        print(1)
    elif K != 2 :
        print(-1)
    else : 
        A = [0] * (N+1)
        idx, ele = 1, K
        for i in range(N) : 
            A[idx] = ele
            idx = ele
            ele += 1
            if ele > N : ele = 2
            if ele == K : ele = 1
        print(*A[1:])