[백준][python] 9658.돌게임4 - DP

• 백준 9658 돌게임4 Silver I
• 문제링크

9658번: 돌 게임 4

나의 접근

N이 1, 2, 3, 4인 경우를 살펴보았을 때 아래와 같은 패턴이 나타난다:

• 돌 1개: 상근, 창영 -> 상근 승
• 돌 2개: 상근, 창영, 상근 -> 창영 승
• 돌 3개: 상근, 창영, 상근, 창영 -> 상근 승
• 돌 4개: 상근, 창영, 상근, 창영, 상근 -> 창영 승

N이 5개인 경우부터는 상근이는 돌 1개, 3개, 4개를 고를 수 있다. 위의 패턴을 토대로 각각의 경우에 대한 승패를 살펴보자면: 

• 돌 1개 (남은 돌 네개) -> 창영 승
• 돌 3개 (남은 돌 2개) -> 창영 승
• 돌 4개 (남은 돌 1개) -> 상근 승

만약 세가지 경우 모두 선공인 상근이가 이기는 경우라면 상근이는 모든 경우에서 질 수 밖에 없게 된다. 하지만 한 가지의 경우라도 상근이가 이기는 경우가 있다면 상근이는 그 경우를 선택할 것이기 때문에 상근이가 이기게 된다!

결론은, 현재 N에서의 N - 1, N - 3, N -4에 대한 상근이의 승패 여부를 구하고, 세개의 경우 중 하나라도 상근이의 승이라면 상근이가 이기게 되며, 그렇지 않으면 창영이가 이기게 된다. 

import sys

N = int(sys.stdin.readline())

def solution(n):
    dp = [0] * (n + 5)
    dp[1], dp[2], dp[3], dp[4] = 0, 1, 0, 1

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

    if dp[n] == 1:
        print('SK')
    else:
        print('CY')
    return dp[-1]

solution(N)