[Python] 8170번 Pebbles (추후 보강 예정)

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

---

 

24/05/19

 

 

스프라그-그런디 문제로, 증명하기가 꽤나 어렵고 규칙을 발견하는 것도 쉽지 않은 문제인 것 같다.

 

나는 이 문제를 해결하기는 했지만, 왜 그렇게 나오는지에 대한 증명은 하지 않아서, 추후에 증명을 하게 된다면 보강해서 작성할 예정이다.

---

 

문제 접근 방식:

 

 

처음에 문제를 접근한 방식은 나이브한 탑-다운 DP였다.

 

가지고 있는 현재 조약돌의 전체 상황을 튜플로 저장하여, 그 상황을 딕셔너리에 집어넣는 풀이였다.

 

당연히 시간초과를 받을 수 밖에 없었는데, 잘 생각해보면 돌 더미의 개수가 최대 $1,000$개이고, 내가 어떤 게임판의 상황에서 할 수 있는 행동 또한 정말 많기 때문에 시간초과가 날 수밖에 없다.

 

그래서 규칙을 찾아서 새로운 게임으로 "변형"해야만 문제가 해결됨을 깨달을 수 있었다.

 

돌 더미의 개수가 6개이고, 각 돌더미의 돌들이 모두 20개씩 있는 경우를 DP로 돌렸고, 그 중에서 그런디 수가 0인, 즉, Cold position인 게임판만 출력하도록 코드를 돌려보았다.

 

그랬더니 다음과 같은 규칙을 발견할 수 있었다.

 

돌 더미의 개수가 짝수 개인 경우, ($2i$번째 돌 더미) - ($2i-1$번째 돌 더미)의 값들을 모두 XOR한 값이 0인 경우에 Cold  position이 됨을 확인할 수 있었다.

 

돌 더미의 개수가 홀수 개인 경우, 첫 번째 돌 더미를 제외하고, 두 번째 돌 더미부터 ($2i+1$번째 돌 더미) - ($2i$번째 돌 더미)의 값들을 모두 XOR한 뒤에, 첫 번째 돌 더미의 돌 개수를 XOR한 값이 0인 경우에 Cold position이 됨을 확인할 수 있었다.

 

이를 토대로 그대로 구현했더니 맞았습니다를 받을 수 있었다.

 

왜 그렇게 작동하는지에 대한 증명은 하지 못한 상황이다. 추후에 증명을 하게 된다면 덧붙여서 작성할 예정이다. 

---

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

# 8170번 Pebbles
# 스프라그-그런디 정리, dp
'''
접근 방법:
탑 다운 DP
'''
import sys
input = sys.stdin.readline
##sys.setrecursionlimit(100_000)
##
##def mex(S):
##    for i, j in zip(sorted(S), range(len(S))):
##        if i != j:
##            return j
##    return len(S)

##DP = dict()
##DP[()] = 0
def solve():
    N = int(input())
    A = tuple(map(int, input().split()))
    # ans = top_down(A)
    ans = 0
    if N % 2 == 0:
        for i in range(N//2):
            ans ^= (A[2*i+1] - A[2*i])
    else:
        ans ^= A[0]
        for i in range(N//2):
            ans ^= (A[2*i+2] - A[2*i+1])
    if ans:
        print('TAK')
    else:
        print('NIE')
'''
def top_down(A):
    if A in DP:
        return DP[A]
    S = set()
    for i in range(len(A)):
        if i == 0:
            if A[1:] not in DP:
                top_down(A[1:])
            S.add(DP[A[1:]])
            for j in range(1, A[0]):
                P = (A[0]-j,) + A[1:]
                if P not in DP:
                    top_down(P)
                S.add(DP[P])
        else:
            limit = A[i] - A[i-1]
            for j in range(1, limit+1):
                P = A[:i] + (A[i]-j,) + A[i+1:]
                if P not in DP:
                    top_down(P)
                S.add(DP[P])
    DP[A] = mex(S)
    return DP[A]
'''
T = int(input())
for _ in range(T):
    solve()