[백준] 11866번 - 요세푸스 문제 0 (파이썬)

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

---

문제

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

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

입력

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

출력

예제와 같이 요세푸스 순열을 출력한다.

문제 탐색하기

N과 K가 주어졌을 때, 1번부터 N번까지의 사람들이 원형으로 앉아 있다. 이때 순서대로 K번째 사람을 제거하는 과정을 반복하여 모든 사람이 제거될 때까지 진행한다. 제거된 사람들의 순서를 출력하면 된다.

코드 설계하기

1부터 N까지의 숫자를 가진 리스트를 생성하고, 현재 제거할 사람의 인덱스를 저장할 변수를 선언한다. 리스트에서 K번째 사람을 제거하고 결과 리스트에 추가한다. 제거된 후 리스트의 길이에 맞게 인덱스를 조절한다. 모든 사람이 제거될 때까지 이 과정을 반복한다.

코드

N, K = map(int, input().split())
people = list(range(1, N + 1))    # 사람들 리스트 생성
result = []    # 제거된 사람들 저장

index = 0 
while people:
    index = (index + K - 1) % len(people)    # 다음 인덱스 계산
    result.append(people.pop(index))    # 사람 제거 및 결과 추가

print("<" + ", ".join(map(str, result)) + ">")