[백준/Python] 9655번(수학, DP, 게임이론)_돌 게임

📌문제 유형

수학, DP, 게임이론 (실버5)

 

📌문제

9655번: 돌 게임

 

📌나의 문제풀이

- 1,3개씩만 가져갈 수 있기 때문에 n이 홀수면 SK, 짝수면 CY가 무조건 이김

n = int(input())

if n % 2 == 0:
    print('CY')
else:
    print('SK')

 

📌 다른사람의 문제풀이

- 돌이 1개 or 3개 남는 순간 승패 결정

[백준 9655, 9656] 파이썬 : 돌 게임

import sys
N = int(sys.stdin.readline())
dp = [-1]*1001
dp[1] = 1
dp[2] = 0
dp[3] = 1
for i in range(4, N+1):
    if dp[i-1] or dp[i-3]:
        dp[i] = 0
    else:
        dp[i] = 1
print('CY' if dp[N] == 0 else 'SK')