[Python] 12848번 막대기 게임

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

---

 

24/05/16

 

 

간단한 스프라그-그런디 정리 응용 문제로, 게임판 분할에 관한 개념을 알고 있으면 쉽게 해결할 수 있는 문제이다.

---

 

문제 접근 방식:

 

 

막대기를 게임판 위에 더 이상 둘 수 없는 사람이 지는 게임이다.

 

다행히도 막대기는 가로 모양 밖에 존재하지 않아서, 각 행 별로 게임이 분리된다는 사실은 쉽게 알 수 있다.

 

또한, 장애물이 있는 곳에는 막대기를 둘 수 없다는 제한 조건 때문에, 장애물이 놓여 있는 곳 별로 게임이 분리된다는 사실 또한 쉽게 알 수 있다.

 

따라서, 각 행 별로, 각 막대기가 놓여진 곳 별로 게임을 분리하여, 각 게임 별 그런디 수를 구하면 된다.

 

$n > k$이고, 길이 $n$짜리 게임 판이 주어질 때, 여기에 길이 $k$짜리 막대기를 놓는다고 하면, 게임판이 분리되는 경우가 생긴다.

 

예를 들어, 길이 $10$짜리 게임 판에 길이 $5$짜리 막대기를 놓는다고 하면, $3$과 $2$로 분리되는 경우가 생긴다.

 

이러한 게임 판 분리 경우도 모두 고려하여 할 수 있는 행동들을 모두 따져주어 그런디 수를 구하면 된다.  

---

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

# 12848번 막대기 게임
# 스그
'''
접근 방법:
스그
'''
import sys
input = sys.stdin.readline

def mex(S):
    for i, j in zip(sorted(S), range(len(S))):
        if i != j:
            return j
    return len(S)

N, M = map(int, input().split())
Game = [list(map(lambda x: len(x), input().rstrip().split('@'))) for _ in range(N)]
K = int(input())
P = sorted(map(int, input().split()))
DP = [0 for _ in range(1001)]
for i in range(1, 1001):
    S = set()
    for j in range(K):
        if i < P[j]:
            break
        else:
            for k in range(i-P[j]+1):
                S.add(DP[k]^DP[i-P[j]-k])
    DP[i] = mex(S)
ans = 0
for i in range(N):
    for j in Game[i]:
        ans ^= DP[j]
print('nein' if ans else 'hyo123bin')