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

문제 링크

---

1. 아이디어

볼록 다각형의 두 꼭짓점을 잇는 선분을 서로 교차하지 않게 번갈아 그으며, 더 이상 그을 수 없는 사람이 지는 게임에서 승자를 구하는 문제로 스프라그 그런디 정리를 활용한다. 선분을 하나 그으면 그 두 끝점은 이후 다른 선분과 끝점에서도 겹칠 수 없으므로 막히고, 나머지 점은 선분의 양쪽에 $a$개와 $n - 2 - a$개로 나뉘며 서로 다른 쪽의 점끼리는 선분이 교차하기 때문에 이을 수 없다. 그래서 양쪽은 서로 독립인 같은 게임이 되고(선분이 변과 일치하면 한쪽이 0개이다), 꼭짓점이 $n$개인 게임의 그런디 수를 $g(n)$이라 하면 $g(0) = g(1) = 0$이고 $n \ge 2$에서 다음과 같다.

\[g(n) = \operatorname{mex}(\{g(a) \oplus g(n - 2 - a) \mid 0 \le a \le n - 2\})\]

$a$와 $n - 2 - a$를 바꿔도 값이 같으므로 절반까지만 구하면 되고, $N$이 최대 1,000이라 $g$를 전부 구한 뒤 $g(N)$이 0이 아니면 선공인 성관이가, 0이면 홍준이가 이긴다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N^2)$	$O(N)$

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

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

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

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

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

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

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

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

    int n;
    cin >> n;

    for (int i = 2; i <= n; i++) {
        memset(seen, 0, sizeof(seen));
        for (int j = 0; j <= (i - 1) / 2; j++) {
            seen[g[j] ^ g[i - 2 - j]] = true;
        }

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

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

---