BOJ 31648 : Palindrome Game

• 문제 링크 : boj.kr/31648
• 난이도 : G5
• 태그 : 애드 혹, 게임이론

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

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

    int T;
    cin >> T;
    while(T--) {
        string s;
        cin >> s;
        if(s.back() == '0') {
            cout << "E\n";
        }
        else {
            cout << "B\n";
        }
    }

    return 0;
}

---

풀이

#24553과 같은 문제이다.

모든 한자리 수는 팰린드롬이다. 0으로 시작하는(끝나는) 팰린드롬은 없다.

따라서 어느 순간 1의 자리가 0이 되면 이 수는 한 번의 시행으로 0으로 만들 수 없고 어떤 팰린드롬을 빼든 1의 자리는 0이 아니게 된다. 그러면 상대방은 다시 1의 자리를 0으로 만들 수 있게 된다. 따라서 1의 자리가 0이 되면 이 순간부터 전체 수가 0이 되기까지 짝수번의 시행이 필요하게 된다. 따라서 1의 자리수를 0으로 만든 사람이 승리하게 된다. 모든 한자리 수는 팰린드롬이므로 첫 시작 수의 1의 자리가 0이라면 Elsie가, 0이 아니라면 Bessie가 된다.