[ BOJ ] 9655 : 돌 게임 ( SILVER 5 ) / C, Python

문제

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

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

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

입력

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

출력

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

풀이 과정

돌이 1개 남았을 때 : 상근이가 돌 1개 가져감 ( 상근 승리 )

돌이 2개 남았을 때 : 상근이가 돌 1개, 창영이가 돌 1개 가져감 ( 창영 승리 )

돌이 3개 남았을 때 : 상근이가 돌 3개 가져감 ( 상근 승리 )

돌이 4개 남았을 때 : 상근이가 돌 1개, 창영이가 돌 3개 가져가거나 상근이가 돌 3개, 창영이가 돌 1개 가져감 ( 창영 승리 )

...

 

돌의 개수가 커지면 커질수록 고려해야 할 경우가 많아지니, 다음과 같이 표기해보도록 하겠다.

돌이 1개 남았을 때 : 선공 승리 ( 현재 턴인 사람이 승리 )

돌이 2개 남았을 때 : 후공 승리 ( 현재 턴이 아닌 사람이 승리 )

돌이 3개 남았을 때 : 선공 승리 ( 현재 턴인 사람이 승리 )

돌이 4개 남았을 때 : 후공 승리 ( 현재 턴이 아닌 사람이 승리 )

 

이렇게 표시하면, 돌이 5개 이상 남았을 때를 계산하기 위해선 다음과 같이 표기할 수 있다.

 

돌이 5개 남았을 때 :

(1) 돌 1개를 가져가면 -> 돌이 4개 남았을 때 상황이 된다.

돌 1개를 상근이가 가져가면, 돌이 4개 남았을 때엔 후공 승리 (현재 턴이 아닌 사람이 승리) 이기 때문에 상근이 승리한다.

즉 돌이 5개 남았을 때 돌 1개를 가져가면 선공 승리이다.

(2) 돌 3개를 가져가면 -> 돌이 2개 남았을 때 상황이 된다.

돌 3개를 상근이가 가져가면, 돌이 2개 남았을 때엔 후공 승리 (현재 턴이 아닌 사람이 승리) 이기 때문에 상근이 승리한다.

즉 돌이 5개 남았을 때 돌 3개를 가져가면 선공 승리이다.

따라서 돌이 5개 남았을 때는 선공 승리이다.

 

돌이 6개 남았을 때 :

(1) 돌 1개를 가져가면 -> 돌이 5개 남았을 때 상황이 된다.

돌 1개를 상근이가 가져가면, 돌이 5개 남았을 때엔 선공 승리 (현재 턴인 사람이 승리) 이기 때문에 창영이 승리한다.

즉 돌이 6개 남았을 때 돌 1개를 가져가면 후공 승리이다.

(2) 돌 3개를 가져가면 -> 돌이 3개 남았을 때 상황이 된다.

돌 3개를 상근이가 가져가면, 돌이 3개 남아쓸 때엔 선공 승리 (현재 턴인 사람이 승리) 이기 때문에 창영이 승리한다.

즉 돌이 6개 나맜을 때 돌 3개를 가져가면 후공 승리이다.

따라서 돌이 6개 남았을 때는 후공 승리이다.

 

이러한 정리를 계속하다보면, 돌이 홀수 개 남았을 때는 선공 승리, 짝수 개 남았을 때는 후공 승리이다.

따라서, 돌이 홀수 개 남았다면 선공인 상근이가 승리하고, 짝수 개 남았다면 후공인 창영이가 승리한다.

C

#include <stdio.h>

int main(void) {
    int n; scanf("%d", &n);
    printf("%s", ((n % 2) ? "SK" : "CY"));
    return 0;
}

Python

print('SK' if int(input()) % 2 else 'CY')