[백준 9658] 돌 게임 4 (Python 풀이, Silver II)

 

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

9658번: 돌 게임 4

 

 흔한 DP 문제다. n이 작을 때는 직접 손으로 처리해주고, 점화식 f(n) = not (f(n-4) and f(n-3) and f(n-1))을 넣어주면 끝.

 @cache 데코레이터를 써서 DP를 자동으로 할 수 있다. 그러나 hashmap을 쓰기 때문에 handwritten DP가 속도가 더 빠를 듯하다.

 

from functools import cache


@cache
def game(n: int) -> bool:
    if n <= 4:
        return [True, False, True, False, True][n]
    return not (game(n - 4) and game(n - 3) and game(n - 1))


print("SK" if game(int(input())) else "CY")