[BaekJoon] 13034번 - 다각형 게임 [Java][C++]

문제 링크

---

1. 아이디어

N개의 꼭짓점으로 이루어진 볼록 다각형에서 선분이 교차하기 않게 그을 때 마지막에 그어서 이기는 플레이어를 찾는 문제로 스프라그 그런디 정리를 활용하면 해결할 수 있다.

N개의 꼭짓점으로 이루어진 볼록 다각형에서 임의의 선분을 처음 그었을 경우 해당 선분을 기준으로 점들이 양쪽으로 나뉜다. 선분이 교차할 수 없으므로 양쪽으로 나뉜 그룹에서 다시 해당 게임이 반복되게 되며 이런 규칙을 통해 그런디 수를 구할 수 있다. 그런디 수를 $g(n)$ 이라 할 때 이동 가능한 다음 상황은 \(g(n) = \operatorname{mex}\{g(0) \oplus g(n - 2), g(1) \oplus g(n - 3), \dots, g(n / 2 - 1) \oplus g(n / 2 - 1)\}\) 이 된다.

---

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

        int n = Integer.parseInt(br.readLine());

        int[] g = new int[1 + n];
        boolean[] vis = new boolean[16];  // 전처리로 미리 크기 계산
        for (int i = 2; i <= n; i++) {
            Arrays.fill(vis, false);

            for (int j = 0; j <= (i - 1) / 2; j++) {
                vis[g[j] ^ g[i - 2 - j]] = true;
            }

            int mex = 0;
            while (vis[mex]) mex++;
            g[i] = mex;
        }

        if (g[n] != 0) {
            System.out.println(1);
        } else {
            System.out.println(2);
        }
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

const int MX = 1000;
int g[1 + MX];
bool vis[16];  // 전처리로 미리 크기 계산

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    for (int i = 2; i <= n; i++) {
        memset(vis, 0, sizeof(vis));

        for (int j = 0; j <= (i - 1) / 2; j++) {
            vis[g[j] ^ g[i - 2 - j]] = true;
        }

        int mex = 0;
        while (vis[mex]) mex++;
        g[i] = mex;
    }

    if (g[n]) {
        cout << 1;
    } else {
        cout << 2;
    }
}

---

3. 디버깅

없음.

---

4. 참고

없음.

---