[BOJ] 11025번: 조세퍼스 문제 3

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

일단 코드 먼저 확인을 해보시면 굉장히 단순함을 알 수 있습니다. 이제 저 코드가 왜 성립하는지를 귀납법으로 증명하겠습니다. 고정된 K에 대해, N = 1일 때 저 코드가 올바른 답을 냄은 자명합니다.

이제 N = N0일 때 저 코드가 올바른 답을 낸다고 가정하고, N0+1에서도 성립함을 보이겠습니다.

N0+1에서 한명을 제거한 뒤의 상태는 아래와 같습니다.

1 2 3 .. K-2 K-1 K+1 K+2 K+3 ... N0+1

이 때, 이 리스트에는 N0개의 원소가 있기 때문에 조세퍼스 문제를 1번부터 시작하는 대신 K+1번부터 시작해서 (N0,K)의 답을 구한다고 생각해도 무방합니다. 그렇게 생각을 하고 보면 코드가 올바른 답을 냄을 알 수 있을 것입니다.

https://github.com/blisstoner/BOJ/blob/master/11025.py