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

문제 링크

---

1. 아이디어

님 게임에서 홀짝 규칙이 추가된 게임으로 짝수 개수만큼 돌을 제거하는 경우는 돌 더미의 모든 돌을 제거할 수 없고, 홀수 개만큼 돌을 제거하는 경우는 돌 더미의 모든 돌을 제거해야 한다.

해당 문제는 돌 더미의 돌의 개수를 약간 조작하면 님 게임과 동치인 게임으로 만들 수 있는데 돌 더미의 돌이 짝수 개인 경우 돌을 두 개 빼버리면 된다. 돌 더미가 8개로 주어졌을 경우 6개를 준 것으로 해석하면 되며, 2개, 4개, 6개를 잘 제거할 수 있어졌다. 돌 더미의 돌이 홀수 개인 경우 돌을 하나 추가해버리면 된다. 돌 더미가 7개로 주어졌을 경우 8개를 준 것으로 해석하면 되며, 2개, 4개, 6개, 8개를 제거하는 선택지가 있다. 여기서 모든 돌 더미의 돌의 수를 2로 나누면 님 게임과 완전히 동일하며 현재 상태로 Nim-Sum을 구해서 승자를 판별해도 된다.

다른 방법으로는 그런디 수를 구해서 해결할 수도 있다.

0부터 그런디 수를 구해보면 아래와 같이 된다.

점화식을 구했으니 각 돌 더미의 돌의 개수에 대한 그런디 수를 구할 수 있으며, 스프라그 그런디 정리로 각 돌 더미에 대한 합 게임으로 볼 수 있으므로 전체 돌 더미의 그런디 수의 XOR 값으로 승패를 판단할 수 있다.

---

2. 코드

1. Nim game [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 % 2 == 0) {
                p -= 2;
            } else {
                p++;
            }

            nimsum ^= p;
        }

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

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

        nimsum ^= p;
    }

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

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

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

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

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

---

3. 디버깅

없음.

---

4. 참고

없음.

---