2023-10-21-동국대SW역량강화캠프-5. 조세퍼스 문제

문제

조세퍼스 문제는 여러 명의 사람들 중 최후의 1인을 고를 때 사용하는 방법이다.

먼저 모인 사람들끼리 특정한 숫자 M을 고른다. 그 다음 한 사람이 숫자 1을 부르고, 그 다음 그 옆에 있는 사람이 2를 부르고 이런 식으로 시계 방향으로 숫자를 하나 씩 불러나간다. 이때 숫자 M의 배수를 부른 사람은 원에서 빠져나간다.

이렇게 한 명씩 원에서 빠져나가 마지막 한 사람이 남을 때까지 이것을 반복한다.

예를 들어, 7명의 사람이 있고 M=3이고, 시계 방향대로 순서대로 1부터 7까지 번호를 붙였을 때 게임의 양상은 아래와 같다.

번호	부른 숫자
1	1
2	2
3	3
4	4
5	5
6	6
7	7
1	8
2	9
4	10
5	11
7	12
1	13
4	14
5	15
1	16
4	17
1	18

이렇게 해서 순서대로 3, 6, 2, 7, 5, 1 번째 사람이 게임에서 나가고 4만 남게 된다.

이런 식 N명의 사람이서 M으로 게임을 진행했을 때 나가는 사람의 순서를 조세퍼스 순열이라고 부른다. 예를 들어 N=7, M=3인 경우 조세퍼스 순열은 3,6,2,7,5,1,4가 된다.

N과 M이 주어졌을 때 (N,M)-조세퍼스 순열을 구하는 프로그램을 작성하여라.

입력

첫째 줄에 N과 M이 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ M ≤ N ≤ 5,000)

출력

예제와 같이 조세퍼스 순열을 출력한다.

예제 1 입력

7 3

예제 1 출력

3 6 2 7 5 1 4

예제 2 입력

6 4

예제 2 출력

4 2 1 3 6 5

---

Source

from collections import deque

q = deque()
li = []

n, m = map(int, input().split())

for i in range(1, n + 1):
	q.append(i)

while(True):
	if(len(q) == 0):
		break
	for i in range(m - 1):
		x = q.popleft()
		q.append(x)
	x = q.popleft()
	li.append(x)

print(*li)