백준 / 돌 게임 / 9655번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 돌 게임 / 9655번 (실버 5단계)

문제 사이트: https://www.acmicpc.net/problem/9655

 

문제 설명

---

나의 풀이

def solution():
    # 돌의 개수
    n = int(input())

    dp = [False] * (n + 4)

    """
    dp[1] = True   (상근이가 1개 가져가서 이김)
    dp[2] = False  (상근이가 1 → 창영이 1 → 상근이 없음 → 패배)
    dp[3] = True   (상근이가 3개 한 번에 가져가서 이김)
    dp[4] = False  (상근이 1 → 창영이 3 or 상근이 3 → 창영이 1 → 항상 창영 승)
    ...
    """

    dp[1] = True
    dp[2] = False
    dp[3] = True

    for i in range(4, n + 1):
        dp[i] = not dp[i - 1] or not dp[i - 3]

    print("SK" if dp[n] else "CY")


if __name__=="__main__":
    solution()

---

※ 알아야 할 것

위 문제는 DP와 게임이론을 포함한 문제입니다!

게임 이론(Game Theory)은 단순히 “게임을 이긴다”를 넘어서, 여러 명의 플레이어가 전략적으로 행동할 때 어떤 결과가 나오는지를 분석하는 수학 이론입니다.