백준 돌 게임 [9655번]

문제

백준 돌 게임

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

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

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

입력

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

출력

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

예제 입출력

입력

5

출력

SK

풀이

import sys
trial=int(sys.stdin.readline())
if(trial%2==1):
    print("SK")
else:
    print("CY")

설명

문제가 너무 간단해서 낚시가 있을거 같지만, 잘 생각해보면 답을 알수 있는 문제이다.

핵심은 1 또는 3 밖에 가져가지 못한다는 것이다. 어쩃든 둘다 홀수이므로, 홀수의 성질을 생각해보자

홀수끼리 두번 더하면 반드시 짝수가되고, 홀수끼리 세번 더하면 반드시 홀수가 된다.

이처럼 계속 더해본다면, 다음과 같은 특징을 쉽게 추출 해낼수 있다.

홀수끼리 짝수번 더하면 반드시 합은 짝수가 되고, 홀수끼리 홀수번 더하면 반드시 합은 홀수가 된다

즉 돌의 갯수가 홀수개라면 => 돌을 가져간다는 행위가 홀수 번 이뤄져야 하므로 상근이가 이기게 되고,

돌의 갯수가 짝수개라면 => 돌을 가져간다는 행위가 짝수 번 이뤄져야 하므로 창영이가 이기게 된다.

따라서 주어지는 돌의 갯수가 홀수 인지 짝수인지에 따라서 출력을 해주면 되는 간단한 문제이다.

DP를 활용한 풀이

DP(다이나믹 프로그래밍)의 개념을 잡기위해서 DP를 이용해서 풀어보자.

동적프로그래밍(Dyanmic Programming) 크고 어려운 문제가 있으면 그것을 먼저 잘게 나누어서 해결한 뒤에 처리하여 나중에 전체의 답을 구한다.→ 이는 분할 정복과 같다.

이 과정에서 Memorization이 사용된다는 점이 분할 정복과 다르다. → 이미 계산한 결과는 배열에 저장!

문제를 다시한번 분석해보자

승자는 마지막에 돌을 가져가는 사람이고, 두 사람은 완벽하게 게임을 진행한다.

그리고 같은 돌의 갯수라도 턴의 갯수는 서로 다를 수 있으므로, 턴의 갯수는 가능한 최소가 되게 한다고 하자.

(즉 돌이 5개일 경우 1개,1개,1개,1개,1개로 가져갈 수도 있지만, 3개,1개,1개로 반드시 가져가는걸로 생각하자. 어차피 결과는 똑같다.)

N을 돌의 갯수라고 하고 DP[N]을 돌의 갯수가 N일떄의 승자가 나오는 최소 턴의 갯수라고 하자.

DP[0]=0, DP[1]=1, DP[2]=2 라고 쉽게 생각 할 수 있다.

그리고 DP[N]= min(DP[N-1]+1 or DP[N-3]+1) 라는 점화식도 구할 수 있다.

왜냐면 돌이 N개일때 사용한 최소 턴횟수는 반드시 돌이 N-1개 일때 이거나 N-3개인 경우에서 +1번을 더 사용한 경우 떄문이다.

import sys
N=int(sys.stdin.readline())
dp = [0] * 1001
dp[0] = 0
dp[1] =1
dp[2]=2

for n in range(3, N+1):
  dp[n] = min(dp[n-1], dp[n-3]) + 1

if dp[N] % 2 == 1:
  print('SK')
else:
  print('CY')