[파이썬] 백준 9655 : 돌 게임

[파이썬] 백준 9655 : 돌 게임

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

9655번: 돌 게임

실버 5

수학, DP

---

두 사람은 돌을 1개 또는 3개를 들고 갈 수 있는 선택권이 있다.

SK가 1개 CY가 1개 = 2개

SK가 1개 CY가 3개 = 4개

SK가 3개 CY가 1개 = 4개

SK가 3개 CY가 3개 = 6개

즉, 두 사람이 모두 돌을 가져가는 한 턴이 끝나면, 두 사람이 가져간 돌의 합은 항상 짝수개가 된다.

 

원래 돌의 개수가 짝수라면, 짝수개를 빼도 짝수가 되고,

원래 돌의 개수가 홀수라면, 짝수개를 빼도 홀수가 된다.

 

예를들어 N = 25라면 돌을 짝수 개씩 제거하고 나면 반드시 1이 남는다.

남은 돌 1개는 SK가 선제턴으로 가져가기 때문에 N이 홀수라면 SK가 승리한다는 조건을 세울 수 있다.

 

만약 N이 짝수라면 게임 마지막에 돌이 남는 것은 0개가 되기 때문에 SK가 가져갈 돌이 없으므로 CY의 승리가 된다.

 

import sys
N = int(sys.stdin.readline())
if N%2 == 0:
    print('CY')
else:
    print('SK')