[BOJ] 9655. 돌 게임(🥈, DP)

문제

돌 게임은 두 명이서 즐기는 재밌는 게임이다.

탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다.

두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다.

풀이

✅ 다이나믹 프로그래밍

중복된 하위 문제들의 결과를 저장하며 풀이해나가는 것

일반적으로 하나의 큰 문제를 작은 문제로 쪼개는 방식을 분할 정복이라고 하는데 다이나믹 프로그래밍(DP, Dynamic Programming)은 그 작은 문제들이 중복되는 문제들이라 그 문제들의 결과를 저장하면 더 큰 문제를 해결할 때 써먹을 수 있다라는 차이가 있다.

즉, 문제의 최적 해결 방법은 부분 문제에 대한 최적 해결 방법으로 구성된다

💡 풀이 아이디어

dp라는 배열을 만들어 인덱스 값 = 돌의 개수로 두기로 했다. 번갈아가며 1개 또는 3개를 가져가게 되는데, 가져가게 되고 남는 돌의 개수의 칸에 1을 넣었다. 일종의 방문처리를 한 셈인데, 이렇게 되면 누가 3개를 가져가고 남은 게 7개인데 7개에 1이 찍혀있게 되면(이미 그 이전에 누군가가 가져가고 남은 숫자였던 것) 3개는 가져갈 수 없게 된다. 그런데 이렇게 되면 매번 그냥 bfs가 된다. dp라는 배열은 단순 visited가 되고 매번 queue에 이전 라운드에서 몇 개의 돌이 남았었는지를 다 저장해둬야 한다. 심지어 라운드 회수를 계산해주는 건 turn 이라는 별개의 변수를 사용하기로 했었다.
dp가 아니라는 생각이 들었음...

🔍 다른 풀이

풀이를 참고

위에서 내가 생각한 방식은 하향식에 가깝고 이 풀이는 상향식이다
찾아보니 dp는 일반적으로 0부터 시작하는 상향식으로 많이 풀게 되고, 하향식의 경우는 재귀를 사용한다고 한다.

어쨌든 이 풀이와 내 풀이의 가장 큰 차이는 다음과 같다

dp라는 배열의 인덱스 값은 돌의 개수
배열의 각 칸에 들어가는 값은 게임의 라운드 회차

dp[3]에 들어가게 되는 값은 돌 3개를 두고 게임했을 때 진행되는 최종 라운드의 횟수. 게임은 1개 또는 3개의 돌을 가져가는 방식으로 진행되므로 1개나 3개를 가져가면 라운드 횟수가 1씩 증가한다. dp[3]은 dp[0](3개에서 3개를 가져가면 0개가 남음)또는 dp[2](3개에서 1개를 가져가면 2개가 남음)의 횟수에 +1은 한 값이 되는 것. 당연히 둘 중 더 작은 값만 가져와서 계산하면 됨

정리하자면 DP 문제에서 dp라는 배열에 넣어야 할 값은

순서대로 이어지는 값 = 배열의 인덱스
최종적으로 구해야 하는 값 = 그 배열의 각 인덱스에 들어갈 값

📝 최종 풀이

N = int(input())

def rock_game():
    dp = [0]*1001
    dp[1], dp[2] = 1, 2

    for i in range(3, N+1):
        dp[i] = min(dp[i-1] ,dp[i-3])+1
    
    # 횟수가 짝수면 CY, 홀수면 SK가 승리한 것
    if dp[N] % 2:
        return 'SK'
    return 'CY'

print(rock_game())