[Python] 16340번 Split Game

 

 

https://www.acmicpc.net/problem/16340

16340번: Split Game

---

 

22/11/13

 

 

전형적인 게임이 분할된 상황에서의 그런디 수를 구하는 문제로, 스프라그-그런디 정리를 충실하게 공부했다면 쉽게 풀 수 있는 문제이다.

---

 

문제 접근 방식:

 

 

외국어 문제이기 때문에 문제 번역을 하자면 아래와 같다.

 

오랫동안, 바이너리 카지노의 부유한 고객들은 새로운 도박을 원했습니다. 그들의 소원을 이루기 위해, 바이너리 카지노의 게임 기획자는 "칩 쪼개기"라는 새로운 게임을 소개했습니다.

이 게임은 손님이 카지노에서 나가려고 할 때만 진행됩니다. 얻었던 칩을 돈으로 전부 교환하는 대신, 카지노의 도전을 수락해서 이 게임에 자신이 얻은 모든 칩을 걸 수 있습니다. 고객이 진다면, 걸었던 모든 칩들은 카지노로 다시 돌아가게 됩니다.

게임이 시작되면 고객은 자신이 걸었던 칩을 $N$개의 더미로 분할합니다. 이때, 각 더미는 항상 같은 칩 개수일 필요는 없습니다.
그런 다음, 고객과 카지노가 서로 돌아가며 게임을 진행합니다. 여기서는 고객이 선 플레이어, 카지노는 후 플레이어입니다.

각 플레이어는 자기 차례가 되었을 때 아래와 같은 행동을 진행합니다.

---

1. 분할할 칩 더미를 하나 고른다.

2. 이 칩 더미의 크기(칩 더미에 있는 칩의 개수) 보다 작은 자연수 $K$를 고른다.

3. 선택한 칩 더미를 가능한 한 많이, $K$크기의 더미들로 분할한다. $K$크기의 더미들로 분할하고 나서 남은 칩들은 또 다른 더미가 된다.

---

각 플레이어는 더 이상 칩 더미를 분할할 수 없을 때 게임에서 집니다.

하지만, 바이너리 카지노의 게임 기획자는 이 게임이 장기적으로 봤을 때 카지노에게 이익을 가져다 줄 지 확신할 수 없습니다. 따라서, 우리가 할 일은 칩 더미가 분할된 초기 상태에 대해서, 각 플레이어가 항상 최적의 플레이를 진행한다고 할 때, 어느 플레이어가 이기는지 알아내는 것입니다.

입력:
첫번째 줄은 더미의 개수 $N$($1 \leq N \leq 2000$)이 주어집니다.
두번째 줄은 $N$개의 더미 각각에 있는 칩 개수 $P_i$($1 \leq P_i \leq 2000$)가 공백으로 분리되어 주어집니다.

출력:
고객(선 플레이어)이 이기면 "First"를, 카지노(후 플레이어)가 이기면 "Second"를 출력하세요.

 

처음에는 그런디 수를 일일이 구해서 규칙을 찾은 후에 그 규칙대로 따라가려는 풀이를 하려고 했다.

 

근데 칩 개수 $P_i$의 범위를 보니 $1$부터 $2000$까지여서 미리 전처리로 $1$부터 $2000$까지의 그런디 수를 전부 구한 뒤에 $XOR$연산을 취해주어도 괜찮을 것 같다는 생각을 했다.

 

문제에서 주어진 것처럼, 분할되는 게임판의 모습은 $K$를 정하면 바로 알 수 있다.

 

분할되는 게임판의 그런디 수는 문제에서 주어진 정보에 따라, $grundy[K]$를 $P_i // K$번 $XOR$연산 한 뒤 $grundy[P_i \% K]$를 $XOR$해주면 구할 수 있다.

 

그리고, $K$의 범위는 칩 개수 $P_i$보다 작은 범위라는 것을 알 수 있으므로, 이것을 $1$부터 $P_i - 1$까지 반복해서 구해준 뒤에, $mex$함수를 취해주면 그 게임판의 그런디 수를 구할 수 있다.

 

 따라서, for문을 3중으로 사용하므로, 전처리하는데에 걸리는 시간은 대략 $O(2000^3)$정도 걸리게 된다.

 

이후에는 그냥 분할된 더미들을 이미 구해놓은 그런디 수들로 그냥 $XOR$연산 취해주면 끝이다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 16340번 Split game
# 게임 이론, 스프라그-그런디 정리
'''
접근 방법:
전처리
'''
# 전처리 구간
def mex(S):
    for num, i in zip(sorted(S), range(len(S))):
       if num != i:
           return i
    return len(S)
grundy = [0, 0, 1, 2]
for i in range(4, 2001):
    S = set()
    for j in range(1, i):
        game = 0
        for _ in range(i//j):
            game ^= grundy[j]
        game ^= grundy[i%j]
        S.add(game)
    grundy.append(mex(S))

import sys
input = sys.stdin.readline

N = int(input())
ans = 0
for i in map(int, input().rstrip().split()):
    ans ^= grundy[i]
print('First' if ans else 'Second')