재미있는 숫자 게임( BOJ 16876 )

문제 : https://www.acmicpc.net/problem/16876

16876번: 재미있는 숫자 게임

 

문제 파악하기

4자리 숫자를 M번의 행동으로 N보다 크게 만들 수 있는지 없는지 판단하는 문제입니다. 설명 중 2명의 플레이어가 항상 최적의 방법으로 게임을 한다고 했습니다. 이는 자신의 차례에서 이기는 경우가 한 번이라도 있는 경우 해당 방법을 사용하겠다는 의미이며, 이는 나중에 탐색을 할 때 중요한 포인트가 됩니다. 이 문제의 경우, 최대 9999까지의 숫자가 나올 수 있으며, 게임을 진행하는 횟수(턴의 수) 또한 100이하이기 때문에 재귀함수와 메모이제이션을 이용하면 해결될 것이라고 유추할 수 있습니다.

 

문제 해결하기

우선, 문제를 상태로 생각하여 재귀함수를 구현해봅시다. 가장 초기 상태는 sv( N, 1 )과 같이 표현할 수 있습니다. 이는 현재 숫자는 N이며, 현재 1번째 턴이라는 뜻입니다. 초기 상태를 구했으니 이번에는 현재 상태에서 나올 수 있는 다음 상태를 생각해봅시다. 예를 들어 sv( 1234, 1 )이라면 나올 수 있는 다음 상태는 어떻게 될까요?

sv( 1235, 2 ) / sv( 1244, 2 ) / sv( 1334, 2 ) / sv( 2234, 2 )

위와 같이 나오게 됩니다. 이렇게 게임이 진행되다가 현재 턴의 수가 M보다 커지게 되면 다음 상태로 넘어가지 않고 탐색을 마무리하게 됩니다. 그리고 이 때, 게임의 승패를 결정하게 됩니다. 우리는 편의상 구사과가 이기면 1, 큐브러버가 이기면 0이라고 합시다. 그렇다면 탐색의 마지막은 다음과 같이 설계할 수 있습니다.

if(t > M) {
        if(n > N) return dp[n][t] = 1;
        else return dp[n][t] = 0;
    }

다음으로, 우리는 현재 상태가 결국 나중에 이길 수 있는 상태인지 아닌지 확인해야 합니다. 이는 문제 파악에서 나왔듯이 현재 상태에서 나올 수 있는 여러 다음 상태 중 하나라도 자신을 이기게 만들어주는 상태가 있는지 확인하면 됩니다. 여기서 중요한 점은 현재 턴에 따라 이긴다는 표시가 달라진다는 점입니다. 구사과의 턴에는 1이 이긴다는 표시이지만 큐브러버의 턴에는 0이 이긴다는 표시이기에 현재 누구의 턴인지에 따라 초깃값과 결괏값이 달라지게 됩니다. 다행히 구사과의 턴은 항상 홀수이며, 큐브러버의 턴은 항상 짝수이기 때문에 모듈러 연산자를 사용하면 쉽게 구현할 수 있습니다.

    // koosaga: 1이면 이김 / cubelover: 0이면 이김
    // >> 초깃값은 지는 경우    
    ret = 1-(t%2);
    for(int i=1;i<=4;i++) {
        inp[i] = (inp[i]+1)%10;
 
        // 자신이 이기는 상태가 하나라도 있는 경우 이김
        if(sv(calc(inp), t+1) == (t%2)) ret = t%2; 
 
        inp[i] = (inp[i]-1+10)%10;
    }
 
    return dp[n][t] = ret;

후기

턴에 따라 이기는 경우가 다르다는 것을 놓치기 쉬운 문제인듯 합니다. 게임 이론을 배울 수 있는 좋은 문제라고 생각합니다.