백준 문제 풀이 - 돌 게임 9655번

📜 문제 이해하기

돌 게임은 두 명이서 즐기는 재밌는 게임이다.
탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다.
두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다.

💡 문제 재정의

돌을 1개 or 3개를 가져갈 수 있고 마지막에 가져갈 수 있는 사람이 이기게 된다. 상근이가 항상 게임을 먼저 시작할 때 이기는 쪽을 출력해라.

✏️ 계획 수립

동적 프로그래밍을 이용해서 풀 수 있다.
남은 돌이 1개가 남았을 때 이기게 된다는 점을 활용하여 문제를 풀면 된다.
즉, 돌이 하나 남았다면 그 다음의 플레이어가 이긴다는 점이다. 돌이 하나 남은 경우는 4개이거나 2개일 때 해당 차례에 있는 사람은 이길 수가 없다. 왜냐하면 1개 또는 3개를 가져가야 하기에 4개일때는 3개를 가져가면 1이 남고 1을 가져가면 3개가 남기때문에 항상 질수 밖에없고 2도 같은 이유이다.
위와 같은 알고리즘으로 아래 문제를 풀 수 있다.

💻 계획 수행

if __name__ == '__main__':
    dp = ['' for _ in range(1001)]
    dp[1] = 'SK'

    for i in range(1, 1000):
        if dp[i] == "SK":
            if dp[i + 1] == '':
                dp[i + 1] = 'CY'
            if i + 3 < 1000:
                dp[i + 3] = 'CY'
        elif dp[i] == 'CY':
            if dp[i + 1] == '':
                dp[i + 1] = 'SK'
            if i + 3 < 1000:
                dp[i + 3] = 'SK'

    print(dp[int(input())])

🤔 회고

사실 이 문제는 홀수와 짝수의 경우로 문제를 풀 수도 있다. 하지만 동적 프로그래밍을 연습하기 위해 DP기법으로 문제를 풀었다.