[BOJ] 1179번: 마지막 조세퍼스 문제

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

M은 별로 크지 않은데 N이 굉장히 커서 뭔가 다른 접근법이 필요합니다. 마찬가지로 귀납적 관점에서 생각하지만, 이전과는 다르게 M, 2M, 3M, 4M, ...을 싹 날린 후의 상태를 생각해봅시다. 예를 들어 (10, 3)의 경우,

1 2 3 4 5 6 7 8 9 10 -> 1 2 X 4 5 X 7 8 X 10의 상태를 생각해보면 이 상황에서 문제를 해결하는 것은 곧

2 3 X 4 5 X 6 7 X 1으로 관점을 바꾸어보았을 때 (7, 3)의 답을 구해서 그것에 대응되는 원래의 값을 찾아주기만 하면 됨을 알 수 있습니다.

일단 계산하기 편하게 M이 N의 약수여서 X가 깔끔하게 떨어지는 경우를 생각해봅시다.

1 2 3 4 5 6 7 8 9 10 11 12

-----------------------------------

1 2 X 4 5 X 7 8 X 10 11 X 을

1 2 X 3 4 X 5 6 X 7   8 X 으로 바꾸어 생각. (8,4) = 6임은 이미 알고있다고 가정.

그러면 6에 대응되는 8이 정답임을 알 수 있고, 6에 8이 대응됨은 (6-1)*M/(M-1)+1을 통해 알 수 있습니다. 이게 왜 되는지는 직접 1, 2, 3, ... 등에 대해 대응이 어떻게 가는지를 확인하면 확인할 수 있을 것입니다.

이제 (10, 3)과 같이 M이 N의 약수가 아닌 경우에는 N%M만큼만 shift 시킨다고 생각하면 됩니다.

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