[Python] 16886번 나누기 게임

 

 

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

16886번: 나누기 게임

---

 

22/11/19

 

 

 

2022.11.22 - [백준 문제 풀이] - [Python] 2737번 연속 합

[Python] 2737번 연속 합

이 문제의 풀이를 응용하여 스프라그-그런디 정리와 함께 풀 수 있는 문제로, 그런디 수를 구하는 문제 중에서는 조금 까다로운 축에 속한다고 볼 수 있는 문제이다.

---

 

문제 접근 방식:

 

 

게임을 진행할 때, 아래 두 가지 규칙을 가지고 진행된다.

 

• 돌 더미 하나를 고르고, 돌 더미 $k$($k \leq 2$) 개로 나눈다.
• 새로 만든 돌 더미에 포함된 돌의 개수를 $a_1, a_2, ..., a_k$라고 했을 때, $a_1>a_2 > ... >a_k>0$, $a_1 - a_2 = a_2 - a_3 = ... = a_{k-1} - a_k = 1$을 만족해야 한다.

 

첫번째 규칙과 두 번째 규칙을 합친다면, 돌 더미에 $N$개의 돌이 있다면, 이를 연속된 $k$개의 정수들로 분할하는 게임이라고 볼 수 있다.

 

2737번의 내용을 한번 다시 상기해보자.

 

우리는 분명 "어떠한 숫자 $N$에서 $k(k+1)/2$을 뺀 후 그 값이 $k$값으로 나눠진다면, 우리는 $N$이 그 등차수열의 일반항에 속해있다고 할 수 있다"라고 했다.

 

 

이를 이용하고, 미리 저장해둔 $grundy$리스트를 이용하여 $i$번째 그런디 수를 구한다.

 

$k$개의 연속된 정수로 $i$개의 돌을 분할한다는 것은 게임판의 상태를 $k$개로 분할한다는 뜻이다.

 

따라서, 만약 $i$개의 돌이 $k$개의 연속된 정수로 분할된다면, 연속된 정수를 이루고 있는 시작 숫자$start$에서 끝 숫자$end$까지의 모든 그런디 수를 전부 $XOR$을 취해준 값이 곧 내가 할 행동으로 인해 생기는 그런디 수이다.

 

이 그런디 수들을 전부 $mex$함수를 취해주면 이번 게임판의 그런디 수를 구할 수 있다.

 

 

여기에 덧붙여서, 선공(구사과)가 이긴다면 가능한 $k$의 값 중에서 가장 작은 값을 출력해야 하므로, 맨 마지막 $N$번째 그런디 수를 구할 때, $k$개의 연속된 정수로 분할될 때의 그런디 수가 $0$이 나온다면 상대방에게 지는 게임판의 상태를 물려주는 것이므로, 이를 만족시키고 제일 먼저 나오는 $k$값을 출력해주면 된다.

---

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

# 16886번 나누기 게임
# 게임 이론, 스프라그-그런디 정리
'''
깡계산
'''
from math import *
N = int(input())
def mex(S):
    for num, i in zip(sorted(S), range(len(S))):
       if num != i:
           return i
    return len(S)
grundy = [0, 0, 0]
min_stone = 0
flag = True
for i in range(3, N+1):
    S = set()
    for n in range(2, floor(sqrt(2*i+1/4)-1/2)+1):
        if (i - n*(n+1)//2)%n == 0:
            total = 0
            if n%2 == 0:
                start, end = i//n - (n//2-1), i//n + (n//2)
            else:
                start, end = i//n - (n//2), i//n + (n//2)
            for j in range(start, end + 1):
                total ^= grundy[j]
            S.add(total)
            if total == 0 and i == N and flag:
                min_stone = end - start + 1
                flag = False
    grundy.append(mex(S))
if grundy[N] == 0:
    print(-1)
else:
    print(min_stone)