[백준] 20301 반전 요세푸스

문제

요세푸스 문제는 다음과 같다.

 1번 사람 오른쪽에는 2번 사람이 앉아 있고, 2번 사람 오른쪽에는 3번 사람이 앉아 있고, 계속하여 같은 방식으로 N$N$명의 사람들이 원을 이루며 앉아 있다. N번 사람 오른쪽에는 1번 사람이 앉아 있다. 이제 K (≤N)번 사람을 우선 제거하고, 이후 직전 제거된 사람의 오른쪽의 K번째 사람을 계속 제거해 나간다. 모든 사람이 제거되었을 때, 제거된 사람의 순서는 어떻게 될까?

이 문제의 답을 (N, K)–요세푸스 순열이라고 하며, (7, 3)–요세푸스 순열은 ⟨3,6,2,7,5,1,4⟩가 된다.

하지만 한 방향으로만 계속 돌아가는 건 너무 지루하다. 따라서 요세푸스 문제에 재미를 더하기 위해 M명의 사람이 제거될 때마다 원을 돌리는 방향을 계속해서 바꾸려고 한다. 이렇게 정의된 새로운 문제의 답을 (N, K, M)–반전 요세푸스 순열이라고 하며, (7, 3, 4)–반전 요세푸스 순열은 ⟨3,6,2,7,1,5,4⟩가 된다.

 N, K, M이 주어질 때, (N, K, M)–반전 요세푸스 순열을 계산해 보자.

입력

첫째 줄에 정수 N, K, M이 주어진다. ($1 \leq N \leq 5\ 000$, $1 \leq K, M \leq N$)

출력

(N, K, M)–반전 요세푸스 순열을 이루는 수들을 한 줄에 하나씩 순서대로 출력한다.

내 풀이

from collections import deque

n, k, m = map(int, input().split())
q = deque(x+1 for x in range(n))

answer = []
cnt = 0 
direction = 1    # default direction
while q:
    if direction == 1:
        for _ in range(k-1):
            q.append(q.popleft())
        answer.append(q.popleft())
    else:
        for _ in range(k-1):
            q.appendleft(q.pop())
        answer.append(q.pop())
        
    cnt += 1
    if cnt%m == 0:
        direction *= -1     # reverse
        
for x in answer:
    print(x)

단, pypy3만 시간 초과 없이 실행 가능

코멘트

제거된 사람의 수를 세는 변수 cnt와 방향을 표시하는 변수 direction 을 이용하는 것이 포인트이다. m명의 사람이 제거될 때마다 (cnt%m==0) -1을 곱해 방향을 바꾼다. 방향을 바꾸는 것은 appendleft와 pop을 이용하면 된다.

반전 요세푸스 문제를 풀기 전에 기본 요세푸스 문제를 풀고 오면 좋다.

References

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

[백준] 11866 요세푸스 문제 0

요세푸스 문제는 다음과 같다.1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모

https://velog.io/@kupulau/%EB%B0%B1%EC%A4%80-11866-%EC%9A%94%EC%84%B8%ED%91%B8%EC%8A%A4-%EB%AC%B8%EC%A0%9C-0