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

 

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

9655번: 돌 게임

 

처음 보자마자 dp로 생각해야겠다고 생각한 문제 

문제를 잘못 읽어서 한참을 헤맸다.. 1 or  2 or  3인줄;;

 

 

dp는 단계적으로 증진될때 사용할 수 있다는걸 다시 한 번 느낄 수 있었던 문제였다..

n = int(input())

dp = [0] * 1001
#0 = 상근 1 = 창영
dp[1] = 0
dp[2] = 1
dp[3] = 0
dp[4] = 1 # 1 3
dp[5] = 0 # 1 3 1
dp[6] = 1 # 1 1 3 1
dp[7] = 0 # 3 1 3

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


if dp[n] == 0:
    print("SK")
else:
    print("CY")