[BaekJoon] #11871 - 님 게임 홀짝 [Java][C++]

문제 링크

---

1. 아이디어

님 게임에 돌을 제거하는 규칙이 추가된 문제로, 짝수 개를 제거할 때는 더미를 전부 비울 수 없고 홀수 개를 제거할 때는 더미를 반드시 전부 비워야 한다. 돌이 짝수 개인 더미는 2개를 빼서 생각하고 홀수 개인 더미는 1개를 더해서 생각하면 모든 더미에서 제거하는 개수가 짝수가 되어 하나의 규칙으로 통일된다. 예를 들어 8개짜리 더미는 6개짜리 더미로 보면 2개, 4개, 6개를 제거할 수 있고, 7개짜리 더미는 8개짜리 더미로 보면 전부 비우는 이동이 8개 제거에 대응하여 2개, 4개, 6개, 8개를 제거할 수 있다. 이제 2개를 한 단위로 보면 일반 님 게임이므로 변환한 값을 2로 나눈 크기로 Nim-Sum을 구하면 되고, 변환한 값이 모두 짝수라서 2로 나누지 않고 그대로 XOR한 값이 0인지 확인해도 결과가 같다.

다른 방법으로는 그런디 수를 직접 구할 수 있다. 홀수 개인 더미는 전부 비우는 이동과 2개씩 제거하는 이동으로 0개와 더 작은 홀수 개 더미에 닿고, 짝수 개인 더미는 2개씩 제거하는 이동으로 0개를 제외한 더 작은 짝수 개 더미에만 닿는다. 이렇게 0개부터 그런디 수를 구해 보면 아래와 같이 된다.

\[g(0), g(1), g(2), \dots, g(8) = 0, 1, 0, 2, 1, 3, 2, 4, 3\] \[g(7) = \operatorname{mex}\{g(0), g(1), g(3), g(5)\} = \operatorname{mex}\{0, 1, 2, 3\} = 4\] \[g(8) = \operatorname{mex}\{g(2), g(4), g(6)\} = \operatorname{mex}\{0, 1, 2\} = 3\]

이 값은 짝수 p에서 p / 2 - 1, 홀수 p에서 (p + 1) / 2이고 앞에서 변환한 값을 2로 나눈 것과 같다. 더미는 서로 독립이므로 스프라그 그런디 정리에 따라 전체 그런디 수는 각 더미의 그런디 수를 XOR한 값이고, 이 값이 0이 아니면 선공이 이긴다.

---

2. 복잡도

접근	시간	공간
님 게임 환원	$O(N)$	$O(1)$
스프라그 그런디	$O(N)$	$O(1)$

($N$ = 입력값 n)

---

3. 코드

풀이 1: 님 게임 환원 [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 % 2 == 0) {
                p -= 2;
            } else {
                p++;
            }

            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 % 2 == 0) {
            p -= 2;
        } else {
            p++;
        }

        nimsum ^= p;
    }

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

---

풀이 2: 스프라그 그런디 [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 % 2 == 0) {
                nimsum ^= p / 2 - 1;
            } else {
                nimsum ^= (p + 1) / 2;
            }
        }

        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 % 2 == 0) {
            nimsum ^= p / 2 - 1;
        } else {
            nimsum ^= (p + 1) / 2;
        }
    }

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

---