# [Platinum III] 다각형 게임 [문제 링크](https://www.acmicpc.net/problem/13034) ## 문제 설명 <p>N개의 꼭짓점으로 이루어진 볼록 다각형이 있다. 다각형의 내각은 모두 180보다 작다. 꼭짓점은 1부터 N번까지 시계 방향으로 번호가 매겨져 있다.</p> <p>성관이와 홍준이는 다각형에서 게임을 하려고 한다. 성관이가 먼저 턴을 갖는다.</p> <p>각 턴마다 플레이어는 두 꼭짓점을 고르고, 선분을 긋는다 (변과 일치해도 된다). 이때, 이미 그려져 있는 선분과 교차하면 안 된다 (선분의 끝 점에서 겹치는 것도 교차하는 것이다). 더 이상 선분을 그릴 수 없는 사람이 게임을 패배한다.</p> <p>N이 주어진다. 두 사람이 최적의 방법으로 게임했을 때, 누가 이기는지 구하는 프로그램을 작성하시오.</p> ## 입력 <p>첫째 줄에 N (3 ≤ N ≤ 1,000) 이 주어진다.</p> ## 출력 <p>성관이가 이기면 1, 홍준이가 이기면 2를 출력한다.</p> ## 풀이 스프라그-그런디 정리를 이용하여 풀었다. 임의의 두 점 사이에 선으로 연결하면 그 점들을 제외한 나머지 점들로 두 게임판이 만들어진다. ``` c++ #include<bits/stdc++.h> using namespace std; int g[1001]; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; for(int i=2;i<=n;i++) { set<int> s; for(int j=0;j<=i-2;j++) s.insert(g[j]^g[i-2-j]); for(int j=0;;j++) { if(!s.count(j)) { g[i]=j; break; } } } cout << (g[n] ? 1 : 2); } ```