BOJ 11694 : 님 게임

• 문제 링크 : boj.kr/11694
• 난이도 : P2

태그 : 게임이론, 스프라그 그런디

---

코드

#include <bits/stdc++.h>

#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 n;
    int ans = 0;
    bool flag = false;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        ans ^= a;
        if(a>1) flag = true;
    }

    if(flag) cout << (ans ? "koosaga" : "cubelover");
    else cout << (!ans ? "koosaga" : "cubelover");

    return 0;
}

---

풀이

마지막에 행동을 하는 사람이 이기는 님 게임에서는 nim sum이 0일때 후공이 이긴다.

마지막에 행동을 하는 사람이 지는 님 게임은 nim sum이 0일 때 임의의 돌 무더기를 추가하거나 0일 아닐 때 0이 되도록 만드는 돌 무더기를 추가하여 변형할 수 있다. 이 경우 nim sum은 뒤집히게 되며 기존의 nim sum이 0이라면 선공이 이기는 것을 알 수 있다.

모든 돌무더기에 돌의 수가 1개인 경우 예외처리를 해주어야 한다.