https://www.acmicpc.net/problem/25179
문제 요약
- 배스킨라빈스 게임
- N을 부르면 짐, 가장 작은 숫자부터 1~M개 가능
- N, M 10^18
접근법
- 웰노운이라고 하지만 나에게는 아님
- 보통 DP로 접근했는데 N, M이 커서 당황
- 자신의 턴에 주어진 숫자로 이길 수 있으면 O 아니면 X
- 31, 3으로 예를 들어보면
- 31 : X
- 28, 29, 30 : O ==> 상대방에게 31을 주는 것이 가능함
- 27 : X ==> 어떻게 하든 상대방이 28 ~ 30 사이로 주어짐
- 24, 25, 26 : O ==> 상대방에게 27을 주는 것이 가능함. 상대방이 27이면 짐
- 여기서 패턴이 보임
- 가장 마지막은 X
- 이후 M개는 O
- 다음은 X, 다음 M개는 O ...
- 이 패턴에서 1이 X인 경우는 X OO...OO X OO.OOO X ... OO..OO X
- 즉 (M + 1)로 나누어서 나머지가 1인 경우 먼저 시작하는 사람이 짐
- 또한 1, 1 + (M + 1), 1 + (M + 1) * 2 ...를 받은 사람도 짐
newbieski