[Python] 7824번 Playing With Stones

 

 

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

---

 

25/06/26

 

 

전형적인 스프라그-그런디 정리 문제이다. 플레티넘 200문제를 달성하기 위해 풀었던 문제들 중 하나이다.

---

 

문제 접근 방식:

 

 

문제가 영어로 되어 있기 때문에, 해석을 하자면 다음과 같다.

 

두 사람이 돌을 제거하는 게임을 함.
$N$개의 돌 무더기가 주어져 있으며, 각각의 무더기에는 $a_1, a_2, \dots, a_n$개의 돌이 있음.
자기 차례에 플레이어는 하나의 무더기에서 최소한 $1$개 이상의 돌을 제거해야하며, 해당 무더기의 돌 개수의 절반 이하만 제거할 수 있음.
이때 돌을 제거할 수 있는 선택이 더 이상 없는 플레이어가 짐.
두 사람이 최적으로 플레이 할 때, 선공이 이긴다면 "YES", 그렇지 않다면 "NO"를 출력하기.

 

각 돌 무더기끼리는 서로 간섭하지 않기 때문에 하나의 돌 무더기에 대해서 그런디 수를 구하고, 이 과정을 모든 무더기에 대해 적용한 뒤에 XOR시켜주면 된다.

 

이제 작은 케이스($N = 15$까지)에 대해서 그런디 수를 구해보자.

 

먼저 $0$개일 때의 그런디 수는 당연히 $0$이다.

$1$개일 때는 절반 이하만 제거할 수 있다는 제한 때문에, 돌을 제거할 수 없으므로 그런디 수는 $0$이다.

$2$개일 때는 최대 $1$개까지 제거할 수 있으므로, 그런디 수는 $\text{mex}(0) = 1$이다.

$3$개일 때는 최대 $1$개까지 제거할 수 있으므로, 그런디 수는 $\text{mex}(1) = 0$이다.

$4$개일 때는 최대 $2$개까지 제거할 수 있으므로, 그런디 수는 $\text{mex}(0, 1) = 2$이다.

$5$개일 때는 최대 $2$개까지 제거할 수 있으므로, 그런디 수는 $\text{mex}(0, 2) = 1$이다.

$6$개일 때는 최대 $3$개까지 제거할 수 있으므로, 그런디 수는 $\text{mex}(0, 2, 1) = 3$이다.

$7$개일 때는 최대 $3$개까지 제거할 수 있으므로, 그런디 수는 $\text{mex}(2, 1, 3) = 0$이다.

$8$개일 때는 최대 $4$개까지 제거할 수 있으므로, 그런디 수는 $\text{mex}(2, 1, 3, 0) = 4$이다.

$9$개일 때는 최대 $4$개까지 제거할 수 있으므로, 그런디 수는 $\text{mex}(1, 3, 0, 4) = 2$이다.

$10$개일 때는 최대 $5$개까지 제거할 수 있으므로, 그런디 수는 $\text{mex}(1, 3, 0, 4, 2) = 5$이다.

$11$개일 때는 최대 $5$개까지 제거할 수 있으므로, 그런디 수는 $\text{mex}(3, 0, 4, 2, 5) = 1$이다.

$12$개일 때는 최대 $6$개까지 제거할 수 있으므로, 그런디 수는 $\text{mex}(3, 0, 4, 2, 5, 1) = 6$이다.

$13$개일 때는 최대 $6$개까지 제거할 수 있으므로, 그런디 수는 $\text{mex}(0, 4, 2, 5, 1, 6) = 3$이다.

$14$개일 때는 최대 $7$개까지 제거할 수 있으므로, 그런디 수는 $\text{mex}(0, 4, 2, 5, 1, 6, 3) = 7$이다.

$15$개일 때는 최대 $7$개까지 제거할 수 있으므로, 그런디 수는 $\text{mex}(4, 2, 5, 1, 6, 3, 7) = 0$이다.

 

이를 통해 규칙을 발견할 수 있는데, 우선 가장 먼저 보이는 규칙은 $N$이 짝수인 경우 그런디 수가 $N/2$라는 점이다.

 

홀수인 경우의 규칙이 무작위처럼 보이는데, 홀수인 경우의 그런디 수만 모아보면 규칙이 보인다.

 

$$0, 0, 1, 0, 2, 1, 3, 0, \dots$$

 

홀수인 경우의 그런디 수 중에서 $0$번째, $2$번째, $4$번째, $6$번째, $\dots$를 보면 $0, 1, 2, 3, \dots$순으로 증가함을 확인할 수 있다.

 

즉, 만약 홀수에서 $1$을 뺀 값이 짝수라면, 그 값의 절반이 그런디 수가 된다.

 

만약 홀수에서 $1$을 뺀 값이 짝수가 아닌 경우에는 어떤 경우일까? 이 경우도 나열하면 다음과 같이 나열할 수 있다.

 

$$0, 0, 1, 0, 2, \dots$$

 

이 또한 위의 홀수인 경우의 규칙과 동일하게 나타난다.

 

따라서, 다음과 같은 방법으로 그런디 수를 구할 수 있다.

 

1. $a_i$가 짝수인지 판단한다.

2. 만약 짝수라면, $a_i$를 $2$로 나눈다. 그리고 그 값이 그런디 수가 된다.

3. 그렇지 않은 경우, 즉, $a_i$가 홀수인 경우, $a_i$에서 $1$을 뺀다. 이후 1번 과정을 반복한다.

 

이 과정을 모든 $a_i$에 대해 반복하여 그런디 수를 구하고, 전부 XOR하여 그 값이 $0$이라면 "YES"를, 아니라면 "NO"를 출력하면 된다.

---

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

# 7824번 Playing With Stones
# 스프라그-그런디 정리
'''
해석:
너와 너의 친구는 돌무더기를 가지고 번갈아가며 돌을 제거하는 게임을 하고 있다.
처음에는 N개의 돌무더기가 있으며, 각각의 무더기에는 a₁, a₂, a₃, ..., aₙ 개의 돌이 있다.
각 턴마다, 플레이어는 하나의 무더기에서 최소한 1개 이상의 돌을 제거해야 하며,
해당 무더기의 돌 개수의 **절반 이하**만 제거할 수 있다.

돌을 제거할 수 있는 유효한 선택이 **하나도 없는** 플레이어는 **패배**하게 된다.
예를 들어, 세 개의 돌무더기에 각각 5개, 1개, 2개의 돌이 있다면, 다음과 같은 선택이 가능하다:

* 첫 번째 무더기(5개)에서는 1개 또는 2개의 돌을 제거할 수 있다. (절반 이하이므로 2개까지 가능)
* 두 번째 무더기(1개)에서는 돌을 제거할 수 없다. (절반이 0.5보다 작기 때문에 1 이상 제거 불가능)
* 세 번째 무더기(2개)에서는 1개의 돌만 제거할 수 있다. (절반은 1)

너는 첫 번째 플레이어이고, 너와 친구 모두 최적의 전략으로 게임을 진행할 때,
**너에게 선제적으로 승리를 보장할 수 있는 수가 있는지**를 판단하라.

즉, 너의 첫 수를 둔 이후 어떤 상황이 오더라도 너가 이길 수 있다면,
그 첫 수는 **"winning move"**(승리 수)라고 한다.
그런 수가 존재하는지를 판단하는 문제다.

접근 방법:
0 -> 0 / 1 -> 0
2 -> 1 / 3 -> 0
4 -> 2 / 5 -> 1
6 -> 3 / 7 -> 0
8 -> 4 / 9 -> 2
10-> 5 / 11-> 1
12-> 6 / 13-> 3
14-> 7 / 15-> 0

짝수 -> N/2가 그런디 수
짝수가 아닌 경우 -> 1을 빼주고 2로 나눈다.
그게 짝수인 경우 -> 그 숫자/2가 그런디 수
아닌경우 -> 위의 과정 반복
'''
import sys
input = sys.stdin.readline

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    grundy = []
    for a in A:
        while True:
            if a % 2 == 0:
                grundy.append(a//2)
                break
            a -= 1
            a //= 2
    res = 0
    for g in grundy:
        res ^= g
    if res == 0:
        print('NO')
    else:
        print('YES')

T = int(input())
for _ in range(T):
    solve()