[Baekjoon 1158] 요세푸스 문제 | Python

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

---

문제

 

원을 그리고 앉아있는 사람들에 차례로 번호를 매기고, 특정 번째 사람을 제거해 나가면서 제거된 사람들의 번호인 요세푸스 순열을 구하는 문제이다.

제거되는 것은 특정 번째를 기준으로 하지만, 각 사람들의 번호는 처음 차례로 매겨진 번호이다.

 

---

풀이

 

주어진 사람들의 리스트에서 주어진 차례의 사람들을 제거해나가면 될 듯 하다. 파이썬에서 원형을 따로 구현하기 보다는 해당 길이보다 차례가 커지면 차례를 조정해주면 될 듯 하다.

그런데 생각해야 하는 것은 사람 한 명을 제거할 때 마다 인덱스로 따지면 두 칸을 이동해야 된다는 것이다. 예를 들어 문제 예시와 같이 7명의 사람과 제거해야 하는 차례가 3인 경우를 생각해 본다면 인덱스에 3을 더할 때는 다음과 같을 것이다. 처음에는 인덱스가 2인 사람을 제거하고, 그 후 인덱스가 5인 사람을 제거하고, 그 후 같은 방식으로 반복될 것이라 생각할 수 있다. 그러나 잘 생각해본다면 인덱스가 2인 사람이 제거되었기 때문에 순서를 생각해본다면 인덱스가 5인 사람은 인덱스가 2인 사람에서 3칸 이동한 사람이 아니라 4칸 이동한 사람이 된다. 따라서 3을 더해주는 것이 아니라 1이 적은 2를 더해서 해당 인덱스의 사람을 제거해주어야 한다.

이러한 작업을 반복해주면서 모든 사람을 제거하고, 제거된 순서대로 각 사람에 처음 번호를 붙여 리스트를 만들어준다면 요세푸스 순열이 될 것이다.

마지막 출력 형식은 join 을 활용하여 처리하였다.

 

---

코드

 

person_n, cut = map(int, input().split())
person = [i for i in range(1, person_n+1)]
ans = []
idx = 0
while len(person) > 0:
    idx += cut - 1
    while (idx >= len(person)):
        idx -= len(person)
    ans.append(person.pop(idx))
print(f'<{", ".join(map(str, ans))}>')