BOJ 16876 - 재미있는 숫자 게임 링크
(2024.03.29 기준 G2)

문제

구사과와 큐브러버는 다음과 같은 게임을 한다.

1. $4$자리 정수 $N$과 턴의 수 $M$을 정한다.
2. 게임은 구사과가 먼저 시작하며, 턴을 번갈아가면서 진행해야 한다.
3. 각 사람은 자신의 턴이 되었을 때, 정수의 숫자 하나를 골라 $1$ 증가시켜야 한다. 고른 숫자가 $9$인 경우에는 $0$이 된다.

게임이 종료된 후에 정수가 $N$보다 커진 경우에는 구사과가, 그 외의 경우에는 큐브러버가 게임을 이긴다. $N$과 $M$이 주어질 때, 승자 출력

알고리즘

게임 이론을 이용한 DP 문제

풀이

현재 숫자를 $n$, 현재 진행된 턴의 수를 $m$이라고 하자. $m$이 홀수이면 큐브러버, 짝수이면 구사과 차례이다.

현재 턴을 가져온 플레이어가 진행시킬 수 있는 방법은 총 $4$가지다. 이 $4$가지 방법 중 하나의 방법이라도 상대 플레이어가 패배한다면, 현재 턴을 가져온 플레이어가 반드시 그 방법으로 진행시키게 된다.

결국은 상대 플레이어가 단 한 번이라도 패배하는 경우가 생긴다면 현재 상태는 현재 플레이어가 이기는 상태이며, 상대 플레이어가 모두 승리한다면 현재 상태는 현재 플레이어가 패배하는 상태가 된다.

턴의 수에 따라 플레이어가 달라짐을 유의한다면, 어렵지 않게 DP로 풀어낼 수 있다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10000, MAXM = 100;

int N, M, dp[MAXN][MAXM];

int dfs(int n, int m){
    if (m == M){
        if (m & 1) // m이 홀수이면 cubelover 차례
            return n <= N; // n이 N보다 작거나 같으면 이긴다.
        else // m이 짝수이면 koosaga 차례
            return n > N; // n이 N보다 크면 이긴다.
    }

    if (~dp[n][m]) return dp[n][m];

    // m+1 턴에서 상대방이 한번이라도 패배하면 현재 턴의 플레이어는 승리한다.
    // 그 상태로 현재 턴의 플레이어는 넘기기 때문이다.
    // m+1 턴에서 상대방이 모두 승리하면 현재 턴의 플레이어는 패배한다.
    dp[n][m] = 0;
    for (int k = 1, nxt; k <= 4; k++){
        if (n % (int)pow(10, k) >= (int)pow(10, k) - (int)pow(10, k - 1))
            nxt = n - (int)pow(10, k) + (int)pow(10, k - 1);
        else
            nxt = n + (int)pow(10, k - 1);
        if (!dfs(nxt, m + 1)) dp[n][m] = 1;
    }

    return dp[n][m];
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;

    memset(dp, -1, sizeof(dp));
    cout << (dfs(N, 0) ? "koosaga" : "cubelover");
}

• Python

import sys; input = sys.stdin.readline

def dfs(n, m):
    if m == M:
        if m & 1: # m이 홀수이면 cubelover 차례
            return n <= N # n이 N보다 작거나 같으면 이긴다.
        else: # m이 짝수이면 koosaga 차례
            return n > N # n이 N보다 크면 이긴다.

    if ~dp[n][m]:
        return dp[n][m]

    # m+1 턴에서 상대방이 한번이라도 패배하면 현재 턴의 플레이어는 승리한다.
    # 그 상태로 현재 턴의 플레이어는 넘기기 때문이다.
    # m+1 턴에서 상대방이 모두 승리하면 현재 턴의 플레이어는 패배한다.
    dp[n][m] = 0
    for k in range(1, 5):
        if (n % 10 ** k) >= 10 ** k - 10 ** (k - 1):
            nxt = n - 10 ** k + 10 ** (k - 1)
        else:
            nxt = n + 10 ** (k - 1)
        if not dfs(nxt, m + 1):
            dp[n][m] = 1

    return dp[n][m]
    
N, M = map(int, input().split())

dp = [[-1] * M for _ in range(10000)]
print('koosaga' if dfs(N, 0) else 'cubelover')