9660(돌 게임 6) - 해결

돌 게임 6

 

문제

 

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

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

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

 

입력

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

 

출력

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

---

게임 이론 문제 였긴 때문에 규칙을 찾기로 하였다.

그래서 1, 3, 4개를 선택할 수 있기 때문에 4 까지는 구해보았다. 

그랬을 때 SK, CY, SK, SK 가 나왔다 그래서 N=5일 때는 N= 1, 2, 4 일 때에서 4개, 3개, 1개를 선택함으로써 N=5를 선택할 수 있기 때문에 해당 과정의 승패를 봤을 때 CY가 있기 때문에 5에서 SK가 이길 수 있는 방법이 있다.

6도 N=2, 3, 5 인 CY, SK, SK이기 때문에 SK가 이길 방법이 있다. 

하지만 N=7 일때는 N=3, 4, 6가 SK, SK, SK이기 때문에 무조건 CY가 이긴다.

이렇게 해봤을 때 SK, CY, SK, SK, SK, SK, CY 가 반복이 된다.

그래서 N % 7이 2, 0일 때 CY이다.

import sys
input = sys.stdin.readline

N = int(input())

if N % 7 == 2 or N % 7 == 0:
    print('CY')
else:
    print('SK')