BOJ 15274 - Multiplication Game 링크
(2024.04.10 기준 P5)

문제

$2$ 이상의 정수 $N$과 정수 $M = 1$이 주어진다. Alice와 Bob이 턴을 번갈아가면서 다음과 같은 게임을 진행한다.

• $N$의 소인수인 $p$를 $M$에 곱한다.
• $M$이 $N$과 같아지면, 현재 턴인 플레이어가 승리한다.
• $M$이 $N$보다 커지면, 두 플레이어는 비긴다.

$N$과 $M$과 선턴인 플레이어가 주어질 때, 게임 결과를 출력

알고리즘

소인수분해 및 상태를 주고 받는 게임 이론

풀이

$N$을 소인수분해부터 하자. 이는 따로 설명하지 않겠다.

소인수분해를 마치면 우리가 살펴봐야 하는 케이스는 총 3가지이다.

1. 소인수가 하나
   $f(i)$를 소인수가 남은 개수가 $i$인 상태라고 하자.
   $f(i)$에서 $f(i-1)$로만 상대방에게 주기만 가능하며, $f(0)$을 주는 사람이 이긴다.
   그러면 결국 $i$가 홀수일 땐 선턴이 이기고, $i$가 짝수일 땐 후턴이 이긴다.

2. 소인수가 둘
   $f(i, j)$를 소인수가 각각 $i$개, $j$개 남은 상태라고 하자.
   $f(i, j)$에서 $f(i-1, j)$나 $f(i, j-1)$을 상대방에게 줄 수 있다. 그리고 $f(0, 0)$을 주는 사람이 이긴다.
   
   소인수의 개수가 동일하다면?
   선턴의 초기 상태가 $f(i, i)$이면 무조건 $f(i-1, i)$만 후턴에게 줄 수 있다.
   후턴은 그 상태에서 $f(i-1, i-1)$을 선턴에게 주게 되면 상태가 반복된다.
   결국은 후턴이 선턴에게 $f(0, 0)$을 주게 되면서 이긴다.
   
   소인수의 개수가 1개 차이라면?
   선턴의 초기 상태가 $f(i-1, i)$이면 후턴에게 $f(i-1, i-1)$을 주게 됨으로써 후턴이 '$f(i, i)$으로 시작하는 선턴의 승패 결과'를 갖게 된다.
   결국은 선턴이 이기게 된다.
   
   이 외에는 $f(i-1, i)$를 상대방에게 주지 않아야 하기 때문에 비기게 된다.

3. 소인수가 셋 이상
   $f(0, 0, \dots, 0)$인 상태를 상대방에게 줘야 이기는데, 상대방이 무조건 하나의 변수를 음수로 만들 수 있기 때문에 무조건 비기게 된다.

코드

• C++

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

typedef long long ll;

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

    int T; cin >> T;
    while (T--){
        ll N; string f; cin >> N >> f;

        // N을 소인수분해
        // 소인수의 개수만 저장
        vector<int> res;
        for (ll d = 2; d * d <= N; d++){
            int ct = 0;
            while (!(N % d)) N /= d, ++ct;
            if (ct) res.push_back(ct);
        }
        if (N > 1) res.push_back(1);

        // 소인수가 하나라면, f(i)를 소인수가 남은 개수가 i인 상태라고 하자.
        // f(i)에서 f(i-1)로만 상대방에게 주기만 가능하며, f(0)을 주는 사람이 이긴다.
        // 그러면 결국 i가 홀수일 땐 선턴이 이기고, i가 짝수일 땐 후턴이 이긴다.
        if (res.size() == 1){
            if (res[0] & 1) cout << f << '\n';
            else{
                if (f[0] == 'A') cout << "Bob\n";
                else cout << "Alice\n";
            }
        }

        // 소인수가 둘이라면, f(i, j)를 소인수가 각각 i개, j개 남은 상태라고 하자.
        // f(i, j)에서 f(i-1, j)나 f(i, j-1)을 상대방에게 줄 수 있다.
        // f(0, 0)을 주는 사람이 이긴다.
        else if (res.size() == 2){
            // 선턴의 초기 상태가 f(i, i)이면 무조건 f(i-1, i)만 후턴에게 줄 수 있다.
            // 후턴은 그 상태에서 f(i-1, i-1)을 선턴에게 주게 되면 상태가 반복된다.
            // 결국은 후턴이 선턴에게 f(0, 0)을 주게 된다.
            if (res[0] == res[1]){
                if (f[0] == 'A') cout << "Bob\n";
                else cout << "Alice\n";
            }
            // 선턴의 초기 상태가 f(i-1, i)이면 후턴에게 f(i-1, i-1)을 주게 됨으로써
            // 후턴이 'f(i, i)으로 시작하는 선턴의 승패 결과'를 갖게 된다.
            // 결국은 선턴이 이기게 된다.
            else if (abs(res[0] - res[1]) == 1) cout << f << '\n';
            // 이 외에는 f(i-1, i)를 상대방에게 주지 않아야 하기 때문에
            // 비기게 된다.
            else cout << "tie\n";
        }

        // 소인수가 셋 이상이라면, f(0, 0, ..., 0)인 상태를 상대방에게 줘야 이기는데
        // 상대방이 무조건 하나의 변수를 음수로 만들 수 있기 때문에
        // 무조건 비기게 된다.
        else cout << "tie\n";
    }
}

• Python

import sys; input = sys.stdin.readline

for _ in range(int(input())):
    N, f = input().split(); N = int(N)

    # N을 소인수분해
    # 소인수의 개수만 저장
    res = []
    d = 2
    while d ** 2 <= N:
        ct = 0
        while not N % d:
            N //= d
            ct += 1
        if ct:
            res.append(ct)
        d += 1
    if N > 1:
        res.append(1)

    # 소인수가 하나라면, f(i)를 소인수가 남은 개수가 i인 상태라고 하자.
    # f(i)에서 f(i-1)로만 상대방에게 주기만 가능하며, f(0)을 주는 사람이 이긴다.
    # 그러면 결국 i가 홀수일 땐 선턴이 이기고, i가 짝수일 땐 후턴이 이긴다.
    if len(res) == 1:
        if res[0] & 1:
            print(f)
        else:
            print('Bob' if f == 'Alice' else 'Alice')

    # 소인수가 둘이라면, f(i, j)를 소인수가 각각 i개, j개 남은 상태라고 하자.
    # f(i, j)에서 f(i-1, j)나 f(i, j-1)을 상대방에게 줄 수 있다.
    # f(0, 0)을 주는 사람이 이긴다.
    elif len(res) == 2:
        # 선턴의 초기 상태가 f(i, i)이면 무조건 f(i-1, i)만 후턴에게 줄 수 있다.
        # 후턴은 그 상태에서 f(i-1, i-1)을 선턴에게 주게 되면 상태가 반복된다.
        # 결국은 후턴이 선턴에게 f(0, 0)을 주게 된다.
        if res[0] == res[1]:
            print('Bob' if f == 'Alice' else 'Alice')
        # 선턴의 초기 상태가 f(i-1, i)이면 후턴에게 f(i-1, i-1)을 주게 됨으로써
        # 후턴이 'f(i, i)으로 시작하는 선턴의 승패 결과'를 갖게 된다.
        # 결국은 선턴이 이기게 된다.
        elif abs(res[0] - res[1]) == 1:
            print(f)
        # 이 외에는 f(i-1, i)를 상대방에게 주지 않아야 하기 때문에
        # 비기게 된다.
        else:
            print('tie')

    # 소인수가 셋 이상이라면, f(0, 0, ..., 0)인 상태를 상대방에게 줘야 이기는데
    # 상대방이 무조건 하나의 변수를 음수로 만들 수 있기 때문에
    # 무조건 비기게 된다.
    else:
        print('tie')