[BaekJoon] 11872번 - 님 게임 나누기 [Java][C++]

문제 링크

---

1. 아이디어

님 게임에서 돌을 제거하는 대신 두 개의 돌 더미로 나누는 방법이 추가된 문제로 스프라그 그런디 정리를 활용하면 해결할 수 있다. 먼저 그런디 수를 구해야 하는데 님 게임처럼 돌을 제거하는 방법은 항상 가능하므로 그런디 수를 $g(n)$ 이라 할 때, $g(n)$ 은 $g(0)$ 부터 $g(n - 1)$ 까지는 고려하며, 돌을 나누는 것은 더 작은 하위 게임 집합이 생기는 것이므로 $g(n)$ 은 $g(1) \oplus g(n - 1)$ 부터 $g(n / 2) \oplus g(n / 2)$ 까지도 고려하면 된다.(돌 더미를 나눌 경우 두 개의 돌 더미에서 진행되는 님 게임으로 치환할 수 있고 이 님 게임의 승패는 역시 XOR로 구할 수 있다.) 따라서 \(g(n) = \operatorname{mex}\{g(0), g(1), \dots, g(n - 1), g(1) \oplus g(n - 1), g(2) \oplus g(n - 2), \dots, g(n / 2) \oplus g(n / 2)\}\) 이 된다.

돌 더미의 크기가 매우 커서 $g(n)$ 을 전부 구할 수가 없는데 규칙성을 보면 N을 4로 나눈 나머지가 0이면 $g(n) = n - 1$ 이고, N을 4로 나눈 나머지가 3이면 $g(n) = n + 1$ 이며 나머지의 경우 $g(n) = n$ 인 것을 볼 수 있다. 따라서 위 점화식을 토대로 모든 돌 더미에 대한 그런디 수의 XOR 값으로 승패를 판단해줬다.

---

2. 코드

1. 풀이 [Java]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int nimsum = 0;

        int n = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        while (n-- > 0) {
            int p = Integer.parseInt(st.nextToken());

            if (p % 4 == 0) {
                nimsum ^= p - 1;
            } else if (p % 4 == 3) {
                nimsum ^= p + 1;
            } else {
                nimsum ^= p;
            }
        }

        if (nimsum != 0) {
            System.out.println("koosaga");
        } else {
            System.out.println("cubelover");
        }
    }
}

2. 풀이 [C++]

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

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

    int nimsum = 0;

    int n;
    cin >> n;

    while (n--) {
        int p;
        cin >> p;

        if (p % 4 == 0) {
            nimsum ^= p - 1;
        } else if (p % 4 == 3) {
            nimsum ^= p + 1;
        } else {
            nimsum ^= p;
        }
    }

    if (nimsum) {
        cout << "koosaga";
    } else {
        cout << "cubelover";
    }
}

---

3. 디버깅

없음.

---

4. 참고

없음.

---