[BOJ 9660] 돌 게임 6

문제 : 턴을 돌아가면서 돌을 1개 ,3개, 또는 4개 가져갈 수 있다. 

마지막 돌을 가져가는 사람이 이긴다.

두 사람이 모두  '완벽하게' 게임을 한다. 누가 이기는 가?

상근이가 게임을 먼저 시작한다. 창영이가 다음으로 한다.

 

돌의 개수는 N개인데 1 ≤ N ≤ 1,000,000,000,000

 

풀이 방법 : 

1개, 3개, 4개 일 때는 한 번에 가져가며 이긴다.

둘 다 돌이 자신의 차례에 1개 , 3개 , 4개가 안 남게 행동을 할 것이다. 

=> 자신의 차례에 2개가 남으면  자신이 이김

https://casterian.net/algo/sprague-grundy.html  (여기를 참고함..)

The Casterian

N=1 상근

N=2 창영

N=3 상근

N=4 상근

N = 5

5 -> 2 -> ... (상근 승)

N = 6

6 -> 2(상) .... : 상근 이김

N = 7

7 -> 6 or 4 or 3  :  창영 이김

N = 8

8 -> 7 .. 상근

N=9 

9 -> 8 6 5 ->.. : 창영

N=10

10 -> 9 7 6 -> : 상근

N=11

11-> 10 8 7 : 상근

N=12 11 9 8 : 상근

N = 13 

12 10 9 : 상근

N=14 

13 11 10 : 창영

 

 N = 7마다 상창상상상상창상창 이 반복됨을 알 수 있습니다.

 

#include <iostream>

using namespace std;

int main()
{
    long long int n;
    cin>>n;
    if(n % 7 == 2 || n % 7 == 0 ) cout<<"CY";
    else cout<<"SK";

    return 0;
}