[백준 -9657] 돌 게임 3

❓ Problem

🤔 How

• DP , 게임이론 문제 이다.

1. DP 테이블에는 n번까지의 돌게임일때 승리하는 경우를 테이블에 저장한다. (1일경우 SK승리 0 일경우 CY 승리)
2. 게임조건중 "완벽하게" 즉 최적의 방법으로 게임을 진행한다.

• 그럼 돌을 1,3,4 개 를 가져가는 경우이후는 다음은 CY(창영)만 다음돌 을 가져 갈 수있다.
• 이를 바탕으로 dp테이블의 1,3,4 개를 이전에서 가져오는경우를 제외하면 다음경우는 반드시 가져올 수 없다.

❗ Solve

#돌 게임 3
import sys
input =sys.stdin.readline

def solution():
    n=int(input())
    dp=[1,1,0,1,1]
    for i in range(5,n+1):
        if (dp[i-4]+dp[i-3]+dp[i-1])==3:
            dp.append(0)
        else:
            dp.append(1)
    print("SK" if dp[n] else "CY")
    pass
if __name__=="__main__": # 실행되는 부분
    solution()
    pass