[Python] 16895번 님 게임 3 / 7685번 Nim

 

 

 

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

16895번: 님 게임 3

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

7685번: Nim

---

 

22/10/09

 

 

두 문제는 입력 형식만 다르고, 풀이 방법이 사실상 완전히 동일한 문제이다.

 

게임 이론, 특히, 스프라그-그런디 정리를 공부하는 중간에 나오는 선행지식들이 요구되는 문제로, 미리 관련 지식들을 공부하면 이 해설을 읽는데 도움이 될 것이다.

---

 

문제 접근 방식:

 

 

님 게임 특성상 하나의 돌무더기에 있는 돌 개수 자체를 그런디 수로 바라볼 수 있다.

 

또한, 우리는 여러 게임판들이 주어질 때, 그것들을 모두 XOR한 것이 그 게임판 그룹의 그런디 수라고 알고 있다.

 

여기의 님 게임은 전형적인 normal게임이기에, 그 게임판 그룹의 그런디 수가 $0$이 아닌 이상 항상 선공이 이긴다.

 

때문에 먼저, 이 게임의 그런디 수를 구해서 이 게임이 선공이 이길 수 있는 게임인지 판단하는 작업을 먼저 거쳐야 한다.

 

선공이 이길 수 없는 게임이라면, (다시 말해 그런디 수가 $0$인 게임이라면) 그냥 $0$을 출력하면 된다.

 

선공이 이길 수 있는 게임이라면, (다시 말해 그런디 수가 $0$이 아닌 게임이라면) 다음과 같이 구현하면 된다.

 

 

 

예를 들어, 돌 무더기가 $3$개가 있고, 첫 번째 돌무더기는 $11$개, 두 번째는 $15$개, 세 번째는 $8$개의 돌이 있다고 해보자.

 

그러면 이 상황에서의 그런디 수는 $11 \oplus 15 \oplus 8 = 12$이다.

 

만약, 선공이 첫번째 돌무더기에서 $4$개의 돌을 가져간다고 한다면, 나머지 돌무더기들은 그대로 있고 첫 번째 돌무더기의 개수만 $7$개로 바뀌므로, 그때의 그런디 수는 $7 \oplus 15 \oplus 8 = 0$이 된다.

 

그리고 후공차례로 넘어가게 된다.

 

결국, 선공이 이기게 하기 위해서는 후공에게 그런디 수가 $0$인 상황을 안겨주도록 게임판을 만들어야 한다.(그런디 수가 $0$인 상황을 맞이하는 사람이 지기 때문에)

 

 

 

이를 이용하여 맨 처음에 구상했던 풀이는 다음과 같다.

 

선공이 돌 무더기 하나를 선택하고, 그 돌무더기에 있는 돌의 개수($P_i$개)만큼 아래와 같은 행위를 반복하여 구한다.

 

돌 $1$개를 가져갔을 때의 그런디 수, 돌 $2$개를 가져갔을 때의 그런디 수,..., 돌 $P_i$개 전부를 가져갔을 때의 그런디 수를 일일이 구해서 각 그런디 수들이 $0$이 되는 순간에 될 수 있는 경우의 수를 $+1$ 시켜준다.

 

 

 

예를 들자면 다음과 같다.

 

아까 전의 예시처럼, 돌무더기 그룹이 $3$그룹 있고, 각 그룹이 $11$개의 돌, $15$개의 돌, $8$개의 돌로 이루어져 있다고 해보자.

 

그러면 선공이 첫번째 그룹($11$개의 돌)에서 돌을 가져간다고 해보자.

 

만약 $1$개의 돌을 가져간다면 그때의 그런디 수는 $10 \oplus 15 \oplus 8 = 13 \neq 0$이므로 아니다.

만약 $2$개의 돌을 가져간다면 그때의 그런디 수는 $9 \oplus 15 \oplus 8 = 14 \neq 0$이므로 아니다.

만약 $3$개의 돌을 가져간다면 그때의 그런디 수는 $8 \oplus 15 \oplus 8 = 15 \neq 0$이므로 아니다.

만약 $4$개의 돌을 가져간다면 그때의 그런디 수는 $7 \oplus 15 \oplus 8 = 0$이므로 가능하다.(이때 $+1$을 해준다)

....

만약 $11$개의 돌을 모두 가져간다면 그때의 그런디 수는 $0 \oplus 15 \oplus 8 = 7 \neq 0$이므로 아니다.

 

만약 선공이 두 번째 그룹($15$개의 돌)에서 돌을 가져간다고 해보자.

 

마찬가지로 그때의 경우의 수들($15$개) 중에서 가능한 경우의 수가 있다면, +1을 해주면 된다.

 

마지막으로 세 번째 그룹($8$개의 돌)에서 돌을 가져간다고 하고, 마찬가지 방법으로 구해주면 된다.

 

이런 식으로 구현을 해서 맞았습니다! 를 받았다.

---

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

# 16895번 님 게임 3
# 게임이론, 스프라그-그런디 정리
N = int(input())
P = list(map(int, input().split()))
total = 0
for i in P:
    total ^= i
if total == 0:
    print(0)
elif len(P) == 1:
    print(1)
else:
    case = 0
    for i in range(len(P)):
        num = 0
        for j in range(len(P)):
            if i == j: continue
            num ^= P[j]
        for k in range(P[i]):
            if num ^ k == 0:
                case += 1
    print(case)

---

하지만, 이 풀이를 조금 더 개선한 방법이 존재하는데, 이는 다음과 같다.

 

위의 풀이를 유심히 관찰을 해보면, 선공이 행동을 한 후의 그런디 수를 구하기 위해서는 기존의 숫자들을 XOR 한 것에서 한 숫자만 바꿔서 XOR을 하면 된다는 사실을 알 수 있다.

 

그리고, 두 번째로 관찰할 수 있는 중요한 사실은 XOR의 연산 특성상 서로 다른 수 두 개를 연산하면 항상 $0$이 아닌 어떤 수가 나온다는 점이다.

 

다시 말하자면, 어떤 두 수를 XOR 연산하여 $0$이 나오려면, 항상 그 두 수는 같은 수여야만 한다.

 

 

 

예를 들어, 첫 번째 그룹에서 돌을 가져가는 경우라고 해보자.

 

위의 풀이에서는 $0 \oplus 15 \oplus 8$부터 $10 \oplus 15 \oplus 8$까지 가능한 경우의 수 중에서 $0$이 나오는 경우의 수를 골랐다.

 

하지만, 이를 첫 번째 사실과 엮어서 관찰하면, $15 \oplus 8 = 7$은 항상 그대로 있고, 바뀌는 것은 맨 왼쪽 부분만 바뀐다는 사실을 알 수 있다.

 

두 번째 사실과 엮어서 관찰을 하면, 결국 $0 \oplus 7$부터 $10 \oplus 7$ 중 $0$이 나올 수 있는 것은 $7 \oplus 7$밖에 없으므로, 전부 다 확인해 보지 않아도, 기껏 해봤자 돌무더기 그룹 하나에서 가져갈 수 있는 경우의 수는 한 가지밖에 없다는 사실을 알 수 있다.

 

이를 요약하자면 다음과 같다.

1. 선공이 가져갈 돌무더기의 번호를 $i$라고 하자.(그 돌무더기의 돌 개수는 $P_i$이다.)

2. i번째 돌무더기를 제외한 나머지 모든 돌무더기를 XOR 해준다. 그리고, 그 XOR값을 $num$이라고 하자.

3. 우리는 $0 \oplus num$부터 $(P_i - 1) \oplus num$중에서 $0$이 될 수 있는 것을 찾아야 된다.
만약, $P_i$가 $num$보다 크거나 같다면, 이 중에 $0$이 될 수 있는 것은 하나뿐이므로 가능한 경우의 수를 $1$ 추가해준다.
만약 그게 아니라면 $0$을 만들 수 없으므로 그냥 지나가면 된다.

4. 이를 모든 돌무더기 번호($1$번부터 $N$번)까지에 대해 실행해준다.

시간 복잡도는 $O(n^2)$인데, 만약 미리 모든 $P_i$들을 XOR 연산해 놓은 것이 있다면($total$), 우리는 $num$을 $total \oplus P_i$를 통해 바로 구할 수 있기 때문에 시간 복잡도 $O(n)$으로 더 빠르게 개선할 수 있다.

---

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

# 시간 복잡도 $O(n^2)$ 버전

# 16895번 님 게임 3
# 게임이론, 스프라그-그런디 정리
import sys
input = sys.stdin.readline
N = int(input())
P = list(map(int, input().rstrip().split()))
total = 0
for i in P:
    total ^= i
if total == 0:
    print(0)
elif len(P) == 1:
    print(1)
else:
    case = 0
    for i in range(len(P)):
        num = 0
        for j in range(len(P)):
            if i == j: continue
            num ^= P[j]
        if num <= P[i]:
            case += 1
    print(case)

# 시간 복잡도 $O(n)$ 버전

# 16895번 님 게임 3
# 게임이론, 스프라그-그런디 정리
import sys
input = sys.stdin.readline
N = int(input())
P = list(map(int, input().rstrip().split()))
total = 0
for i in P:
    total ^= i
if total == 0:
    print(0)
elif len(P) == 1:
    print(1)
else:
    case = 0
    for i in range(len(P)):
        if total^P[i] <= P[i]:
            case += 1
    print(case)

# 7685번 Nim
# 게임이론, 스프라그-그런디 정리
import sys
input = sys.stdin.readline

while True:
    N = int(input())
    if N == 0:
        break
    P = list(map(int, input().rstrip().split()))
    total = 0
    for i in P:
        total ^= i
    if total == 0:
        print(0)
    elif len(P) == 1:
        print(1)
    else:
        case = 0
        for i in range(len(P)):
            num = 0
            for j in range(len(P)):
                if i == j: continue
                num ^= P[j]
            if num <= P[i]:
                case += 1
        print(case)