[BaekJoon] #18937 - 왕들의 외나무다리 돌게임 [Java][C++]

문제 링크

---

1. 아이디어

$N$개의 외나무다리에서 흰 왕과 검은 왕이 번갈아 자기 돌을 움직이며, 움직일 수 없는 왕이 지는 게임의 승자를 구하는 문제로 스프라그 그런디 정리를 활용한다. 한 다리에서 두 돌 사이의 빈 칸 수를 더미의 돌 개수로 보면, 자기 돌을 상대 쪽으로 움직이는 것은 그 더미에서 돌을 하나 이상 제거하는 것과 같고 두 돌이 붙으면 더 줄일 수 없는 빈 더미가 된다. 움직이는 돌이 왕마다 정해져 있어도 두 왕이 할 수 있는 이동이 빈 칸 수의 관점에서는 같으므로 님 게임으로 볼 수 있고, 다리 한 개의 그런디 수는 빈 칸 수인 $A_i - 2$이다.

문제는 멀어지는 방향으로도 움직일 수 있다는 점인데, 한 왕이 돌을 $d$칸 멀어지게 하면 상대 왕이 자기 돌을 같은 $d$칸 따라가서 빈 칸 수를 원래대로 되돌릴 수 있다. 돌이 다리 끝에 닿으면 더 멀어질 수 없으므로 이런 후퇴는 유한 번만 일어나고, 따라서 님 게임에서 이기는 쪽이 후퇴 이동에도 응수해 계속 이길 수 있다. 결국 모든 다리의 $A_i - 2$를 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 x = Integer.parseInt(st.nextToken());
            nimsum ^= x - 2;
        }
        boolean whiteFirst = br.readLine().equals("Whiteking");

        if (nimsum != 0) {
            if (whiteFirst) {
                System.out.println("Whiteking");
            } else {
                System.out.println("Blackking");
            }
        } else {
            if (whiteFirst) {
                System.out.println("Blackking");
            } else {
                System.out.println("Whiteking");
            }
        }
    }
}

#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 x;
        cin >> x;
        nimsum ^= x - 2;
    }

    string s;
    cin >> s;
    bool white_first = s == "Whiteking";

    if (nimsum) {
        if (white_first) {
            cout << "Whiteking";
        } else {
            cout << "Blackking";
        }
    } else {
        if (white_first) {
            cout << "Blackking";
        } else {
            cout << "Whiteking";
        }
    }
}

---