2018. 4. 25. 20:37, 알고리즘/BOJ
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)의 답을 구한다고 생각해도 무방합니다. 그렇게 생각을 하고 보면 코드가 올바른 답을 냄을 알 수 있을 것입니다.
'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ] 1562번: 계단 수 (0) | 2018.04.26 |
---|---|
[BOJ] 1305번: 광고 (0) | 2018.04.26 |
[BOJ] 1179번: 마지막 조세퍼스 문제 (0) | 2018.04.25 |
[BOJ] 1168번: 조세퍼스 문제 2 (2) | 2018.04.25 |
[BOJ] 1040번: 정수 (2) | 2018.04.25 |
[BOJ] 1134번: 식 (0) | 2018.04.24 |
Comments