백준 | 돌 게임

백준 돌 게임 문제 풀이이다.

창영이와 상근이는 돌 n개로 마지막 돌을 가져가는 사람이 이기는 게임을 하고 있다.

항상 상근이부터 게임을 시작하고, 각 턴에서 1개 또는 3개의 돌을 가져갈 수 있을 때 승자를 출력하는 문제이다.

돌이 4개인 경우를 생각해보자.

먼저 상근이가 1개의 돌을 가져가면 3개의 돌이 남는다.
이때 창영이는 3개의 돌을 가져갈 수 있고, 마지막 돌을 챙겼으므로 승자가 된다.

만약 창영이가 1개의 돌을 가져간다면 어떻게 될까?

그러면 2개의 돌이 남는데, 이때 상근이는 2개를 가져감으로써 승자가 될 순 없다.
왜냐하면 정확히 1개 또는 3개의 돌을 가져가야 하기 때문이다.

따라서 돌이 2개 남은 상황에서 상근이는 1개의 돌만 가져갈 수 있고, 이제 마지막 돌을 챙긴 창영이가 승자가 된다.

이를 정리하면 규칙을 찾을 수 있을까?

상근이와 창영이가 한 번씩 돌을 챙겨가면 무조건 짝수 개의 돌이 사라진다.
(1개 + 1개, 1개 + 3개, 3개 + 1개, 3개 + 3개만 가능하므로!)

이는 다르게 말하면 홀수 개(짝수 개 + 1개)의 돌이 있다면, 어떤 경우든 마지막 1개의 돌은 상근이가 가져가게 된다는 것이다.

또한, 홀수 개일 때는 마지막 돌을 창영이가 가져가게 되는 것이므로, 짝수 개(홀수 개 + 1개)의 돌이 있다면, 마지막 1개의 돌은 창영이가 가져가게 된다.

따라서 이 게임은 돌의 개수에 따라 승패가 정해지는 게임이고, 돌이 짝수 개라면 창영이가, 홀수 개라면 상근이가 승리하게 된다.

코드(정답)는 다음과 같다.

import sys


n = int(sys.stdin.readline())

if (n % 2) == 0:
    print("CY")
else:
    print("SK")