[BOJ 9660] 돌 게임 6

문제 링크 : https://www.acmicpc.net/problem/9660

문제

돌 게임은 두 명이서 즐기는 재밌는 게임이다.

탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개, 3개 또는 4개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다.

두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1,000,000,000,000)

출력

상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다.

제한

시간 제한	메모리 제한
1sec	128MB

---

풀이

두 사람이 돌을 $1, 3, 4$개씩 가져가며 마지막 돌을 가져가는 사람이 승리하는 게임이다. 돌의 개수 $N$이 최대 $10^{12}$에 달하므로 일반적인 DP로는 풀 수 없고, 승패의 규칙성(주기성)을 찾아야 한다.

게임 이론에 따라 돌의 개수가 $n$일 때의 승패를 분석하면, 특정 주기로 승패가 반복됨을 알 수 있다. 이 게임에서는 주기가 $7$로 나타나며, $n \pmod 7$의 값이 $0$이거나 $2$인 경우에만 후공인 상근(CY)이 승리하고 그 외에는 선공인 상근(SK)이 승리한다.

\[n \pmod 7 = 0 \text{ or } 2 \implies \text{CY win}\]

따라서 $N$을 $7$로 나눈 나머지를 확인하여 상근(SK)과 창영(CY) 중 누가 승리할지 즉시 결정할 수 있다.

소스코드

Github Link : Source Code

참고 알고리즘 :