백준 3596 (C++) 크로스와 크로스

최초 업로드: 2025-09-13 12:07:42

최근 수정 시간: 2025-09-13 12:07:42

게시자: rlatjwls3333

카테고리: 백준

# [Platinum II] 크로스와 크로스

[문제 링크](https://www.acmicpc.net/problem/3596)

## 문제 설명

크로스와 크로스 게임은 1 × n칸으로 이루어진 보드에서 진행한다. 두 플레이어는 서로 번갈아가면서 게임을 한며, 각 칸의 크기는 1 × 1이다.

각 플레이어는 자기 턴일때, 빈 칸중 한 곳에 '×' 마크를 한다.

만약, 어떤 플레이어가 연속된 3개의 '×'를 만들 수 있다면 그 플레이어가 이긴다.

n이 주어졌을 때, 두 플레이어가 현재 턴에서 선택할 수 있는 가장 좋은 방법으로 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오.

## 입력

첫째 줄에 n이 주어진다. (3 ≤ n ≤ 2000)

## 출력

첫 번째 플레이어가 이긴다면 1을, 두 번째 플레이어가 이긴다면 2를 출력한다.

## 풀이
스프라그-그런디 정리를 공부하며 풀었다. 3칸, 4칸, 5칸씩 지워지는 모든 상태 (그런디 수)를 전부 구한 후, mex를 취해 0이 아니면 1이 승리, 0이면 2가 승리로 두었다.

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

const int MAX = 2001;

int g[MAX];

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

for(int i=1;i<=n;i++) {
 set<int> grundies;
 grundies.insert(g[max(0, i-3)]);
 grundies.insert(g[max(0, i-4)]);
 for(int j=0;j<=i-5;j++) grundies.insert(g[j]^g[i-5-j]);

for(int j=0;;j++) {
 if(!grundies.count(j)) {
 g[i]=j;
 break;
 }
 }
 }
 cout << (g[n] ? 1 : 2);
}
```