백준9655 문제 보러가기

문제

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

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

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

입력

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

출력

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

예제 입력 1

5

예제 출력 1

SK

문제해결

DP는 점화식? 규칙 찾기?

문제는 간단했다. 1개 또는 3개씩 돌을 가져가는데, 지난 문제에서 점화식을 찾아서 해결했기 때문에 이번에도 그것을 찾기 위해서 규칙을 찾기 시작 했다.
처음에는 상근이가 시작을 한다고 했다.

N = 1
[1(상근)] -> SK
N = 2
[1(상근), 1(창영)] -> CY
N = 3
[1(상근), 1(창영), 1(상근) / 3(상근)] -> SK
N = 4
[1(상근), 1(창영), 1(상근), 1(창영) / 1(상근), 3(창영) / 3(상근), 1(창영)] -> CY
...

3 부터 1과 2의 조합이라고 생각했다.
N을 1과 3의 더하기 연산으로 구성한다고 생각했다.

N = 1
1 = 1(1번)
N = 2
2 = 1 + 1(2번)
N = 3
3 = 1 + 1 + 1(3번) = 3(1번)
N = 4
3 = 1 + 1 + 1 + 1(4번) = 1 + 3(2번) = 3 + 1(2번)
N = 5
5 = 1 + 1 + 1 + 1 + 1(5번) = 1 + 1 + 3(3번) = ...
...

숫자를 구성하는 개수가 상근이와 창영이가 돌은 던지는 횟수라고 생각을 했고 그 횟수가 홀수면 무조건 상근이가 승, 짝수면 무조건 창영이가 승리하는 방식이다. N이 어떤 숫자건 간에, 짝수면 짝수 번 던지게 되고, 홀수면 홀수 번 던지게 되는 사실을 알게 되었다.

따라서 N이 홀수면 상근이가 승, 짝수면 창영이가 승리하게 된다.
따라서 코드는 다음과 같다.
매우 간단하다.

N = int(input())

if N % 2 == 1 :
    print("SK")
else :
    print("CY")