📖 문제 읽기

Alice와 Bob이 게임을 하는데 규칙은 다음과 같다.

1. 처음에 1로만 구성된 보드를 받는다.

2. 차례인 사람은 보드에서 최소 2개 이상의 동일한 정수를 골라서 지우고 그 합을 보드에 포함시킨다.

3. 더 이상 진행을 할 수 없을 때(보드에 동일한 정수가 없을 때) 해당 차례의 사람이 우승한다.

4. Alice와 Bob 모두 매 순간 최선의 선택을 한다.

5. 게임은 Alice부터 시작한다.

📊 문제 분석

매 순간 최선의 선택을 한다는 것은 가능한한 본인이 우승할 수 있는 방향으로 게임을 진행시키고자 하는 것이다. 이 게임에서는 자신의 차례에서 더 이상 동일한 정수가 보드에 없을 때 우승하므로, 본인의 순서에서는 다음 사람이 지울 수 있는 정수가 있도록(동일한 정수가 남아 있도록) 해야한다.

💡 아이디어 도출

처음 보드에는 1만 있다. 문제의 조건에 따라 1이 두 개 있을 때부터 적어보며 규칙을 찾아보자.

1 1 [Alice] ➡️ 2 [Bob] : Bob 우승

1 1 1 [Alice] ➡️ 1 2 [Bob] : Bob 우승

1 1 1 1 [Alice] ➡️ 1 1 2 [Bob] ➡️ 2 2 [Alice] ➡️ 4 [Bob] : Bob 우승

1 1 1 1 1 [Alice] ➡️ 1 1 3 [Bob] ➡️ 2 3 [Alice] : Alice 우승

1 1 1 1 1 1 [Alice] ➡️ 1 1 4 [Bob] ➡️ 2 4 [Alice] : Alice 우승

...

1이 n개 [Alice] ➡️ 1 1 n-2 [Bob] ➡️ 2 n-2 [Alice] : Alice 우승

즉, 1이 5개 이상일 때부터는 Alice는 첫 번째 차례에서 최선의 선택으로 1을 두 개 남기고 n-2개의 1을 다 더한 값으로 바꾸는 필승 전략을 택할 수 있다.

⌨️ 코드

#include <bits/stdc++.h>
 
using namespace std;
 
string solve(int n){
    if(n<5) return "Bob\n";
    return "Alice\n";
}
 
int main()
{
    int t, n;
 
    cin>>t;
    while(t--){
        cin>>n;
        cout<<solve(n);
    }
}