[백준 2024/10/18] 9655번 돌 게임

1. 문제

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

 

2. 접근 방법

[0,0] 을 Idx로 가지는 리스트를 선언하여 시작하였다.

만약 sk가 n번째 돌을 가져갔다면 cy은 n+1 or. n+3 번째 돌을 가져갈 수 있다고 생각하여 이를 이용하여 코드를 작성해 주었다.

위 코드대로 작성하게 되면 시간초과가 나므로, 

 

    if dp[n][name] > 0:
        return

이 부분을 추가하여 중복된 계산을 피하고자 하였다.

 

3. 코드

def get_winner(n, name):
    if n > x:
        return
    if dp[n][name] > 0:
        return

    dp[n][name] += 1

    if name == 0:
        get_winner(n+1, 1)
        get_winner(n+3, 1)
    else:
        get_winner(n+1, 0)
        get_winner(n+3, 0)


if __name__ == "__main__":
    x = int(input())
    dp = [[0, 0] for _ in range(x+1)]
    get_winner(1, 0)

    if dp[x][0] > 0:
        print("SK")
    else:
        print("CY")