[백준/python] 9655번: 돌게임

문제

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

예시

코드

n = int(input())

dp = [-1] * 1001

dp[1] = 1 # SK
dp[2] = 0 # CY
dp[3] = 1 # SK


for i in range(4, n+1):
    if dp[i-1] != 1 or dp[i-3] != 1: 
        dp[i] = 1
    else:
        dp[i] = 0

if dp[n] == 1:
    print("SK")

else:
    print("CY")

풀이

상근이가 이기는 경우를 1, 창영이가 이기는 경우를 0이라고 두었다

n개의 돌이 있을 때,

맨 처음 상근이가 1개의 돌을 가져가면 남은 돌은 n-1개이고 게임의 결과는 dp[n-1]의 반대이다.

(dp 내의 결과는 상근이가 시작했을 때의 결과고, 다음은 창영이 차례이므로...) 

맨 처음 상근이가  3개의 돌을 가져가면 남은 돌은 n-3개이고 게임의 결과는 dp[n-3]의 반대이다.

즉, dp[n-1] 이나 dp[n-3]이 1이 아니면 dp[n]은 1이다.