11866번: 요세푸스 문제

요즘 플러터와 자바, 파이썬을 병행하다보니 눈알이 따로 노는 것만 같은 기분이 든다.
매일마다 백준 문제 한 문제씩 파이썬으로 코딩테스트를 공부중인데 오늘은 요세푸스 문제를 풀어봤다.
11866번: 요세푸스 문제

요세푸스 순열

순열에 관한 이 문제는 유대의 역사가였던 요세푸스(Favius Josephus, 37?~100?)가 겪은 흥미로운 일화에서 유래되었다고 한다.

요세푸스는 제1차 유대-로마 전쟁(AD 66~77) 당시 동료 40명과 함께 요타파타에서 로마군에게 포위되자 명예로운 죽음을 선택하기 위해 다음과 같은 방법을 결정했다.

요세푸스를 포함하여 41명이 원으로 둥글게 앉은 다음, 3번째 사람이 죽는 방법을 계속 반복을 하여 아무도 남지 않을 때까지 계속하기로 했다. 그러나 요세푸스는 마지막까지 살아남았다고 한다. 요세푸스는 어떻게 살아남은 것일까?

41명을 원 모양으로 둥글게 앉힌 후 1번에서 41번까지 번호를 붙인다. 그리고 1에서부터 3의 배수가 되는 순서에 앉아 있는 사람부터 죽기 시작했다.
[출처] 요세푸스와 순열_살아남은 자의 수학 공식|작성자 엔젤리나
머리가 좋으면 이런 일도 피해갈 수 있나보다. 아마 나는 죽은 사람 중 한명이 될 것 같다.ㅎㅎ

<내 풀이>

n,m = map(int, input().split())
circle_list = []
ans_list = []
number = 0
for i in range(n):
    circle_list.append(i+1)

def num_divide(num, circle_list_len):
    if (circle_list_len-1 < num):
        while (circle_list_len-1 < num):
            num = num % circle_list_len
    return num
    
for i in range(n):
    circle_list_len = len(circle_list)
    number = num_divide(number+(m-1) , circle_list_len)
    ans_list.append(circle_list[number])
    del circle_list[number]
print("<" + ", ".join(map(str,ans_list)) + ">")