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

문제 링크

---

1. 아이디어

스프라그 그런디 정리를 통해 해결할 수 있는 문제로 두 돌이 서로 가까워지는 방향으로만 이동한다고 했을 때, 그런디 수를 구하면 두 돌 사이의 간격을 님 게임의 돌 더미의 돌의 개수와 동일하게 볼 수 있으니 $g(n) = n - 2$ 가 된다. 해당 문제는 돌이 서로 멀어지는 방향으로도 이동할 수 있는데 이때 내 돌이 상대방으로부터 멀어진만큼 상대방 돌도 내 돌 쪽으로 이동할 수 있고 이 경우 두 돌 간 거리 차이는 똑같으며 서로 이동하기 전 상태와 승패에 변함이 없다.

---

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 x = Integer.parseInt(st.nextToken());
            nimsum ^= x - 2;
        }
        boolean isWhiteKingName = br.readLine().equals("Whiteking");

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

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

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

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

---

3. 디버깅

각 플레이어가 취하는 행동이 다를 수 있음에도 impartial game으로 간주해서 스프라그 그런디 정리를 적용할 수 있는게 약간 아리송했는데, 두 돌 사이의 간격에 대한 제거 게임으로 간주하면 impartial game으로 볼 수 있는 것 같기도 했다.

---

4. 참고

없음.

---