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

문제 링크

---

1. 아이디어

님 게임에서 돌 더미 하나를 비어 있지 않은 두 더미로 나누는 이동이 추가된 문제로, 더미마다 그런디 수를 구해 XOR하는 스프라그 그런디 정리로 해결한다. 돌이 $n$개인 더미의 그런디 수를 $g(n)$이라 하면 돌을 제거하는 이동은 항상 가능하므로 $g(0)$부터 $g(n - 1)$까지로 갈 수 있고, 더미를 $a$개와 $n - a$개로 나누면 서로 독립인 두 게임의 합이 되어 그런디 수가 $g(a) \oplus g(n - a)$이다. 따라서 $g(n)$은 이 값들을 모두 모은 집합의 mex이다.

\[g(n) = \operatorname{mex}(\{g(0), g(1), \dots, g(n - 1)\} \cup \{g(a) \oplus g(n - a) \mid 1 \le a \le \lfloor n / 2 \rfloor\})\]

더미의 크기가 최대 $2 \times 10^9$이라 점화식으로 $g(n)$을 전부 구할 수 없는데, 작은 $n$부터 직접 구해 보면 $n$을 4로 나눈 나머지가 0이면 $g(n) = n - 1$, 3이면 $g(n) = n + 1$, 그 외에는 $g(n) = n$이라는 규칙이 보인다. 이 규칙으로 모든 더미의 그런디 수를 구해 XOR한 값이 0이 아니면 선공이 이기고 0이면 후공이 이긴다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N)$	$O(1)$

($N$ = 입력값 n)

---

3. 코드

풀이 [Java][C++]

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");
        }
    }
}

#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";
    }
}

---