[Python] 2600번 구슬게임

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

---

 

24/05/13

 

 

단순한 님 게임의 변형으로 해결할 수 있는 문제다. 스프라그-그런디 정리를 배우면서 님버에 대한 개념을 익혔다면 쉽게 해결할 수 있는 문제다.

 

그 외에도 이차원 DP로도 해결할 수 있다.

---

 

문제 접근 방식:

 

 

나는 이 문제를 스프라그-그런디 정리를 공부하며 얻은 지식인 님버를 활용하여 문제를 해결했다.

 

결국 이 문제는 님 게임의 변형이고, 처음 두 통에 들어 있는 구슬의 수가 최대 $500$개로 제한되어있기 때문에 충분히 빠른 시간 안에 님버를 구할 수 있다.

 

또한, 내 차례 때 할 수 있는 행동의 가지 수가 최대 $3$가지이기 때문에 각 숫자 별로 구하는 님버가 최대 $3$까지임을 확인할 수 있다.

 

현재 게임 판의 님버를 구하는 것은 내가 행동함으로써 바꿀 수 있는 판들의 님버들의 MEX값을 구하면 된다.

 

우리는 게임 2개를 동시에 진행하고 있으므로, 구한 님버 2개를 XOR하여 0을 넘으면 선공이 이기고, 0이라면 후공이 이긴다고 판단하면 된다.

 

 

반면 굳이 그렇게 풀지 않아도 동시에 하는 게임이 2개 밖에 없기 때문에, 2차원 DP를 돌려도 충분하다.

$$DP[i][j] = i\text{개의 돌과 }j\text{개의 돌이 남았을 경우}$$

선공이 이기는 상황이라면 위의 DP식의 값을 1로, 후공이 이기는 상황이라면 위의 DP식의 값을 0으로 설정하면 된다.

 

이후 그냥 게임 DP문제를 풀던 것 처럼 그냥 탑다운 DP를 하거나 바텀업 DP를 돌리면 된다.

내가 할 수 있는 행동도 세 가지 밖에 없으므로, 쉽게 돌릴 수 있다.

 

내가 선공이고 상대방이 후공이라고 해보자.

 

내가 어떤 행동을 해서 게임 판을 바꾼다면, 내가 후공이 되고 상대방이 선공이 된다.

 

따라서 어떤 게임 판에서 내 행동으로 인해 후공이 이기는 상황으로 만들 수 있다면, 사실 그건 내가 이기는 상황으로 만들 수 있다는 뜻이므로, 이를 이용하여 구현하면 된다.(게임 DP를 풀었다면 이러한 개념은 다들 알 것이지만, 혹시나 해서...) 

---

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

# 2600번 구슬게임
# DP, 게임이론
'''
접근 방법:
게임 DP
'''
import sys
input = sys.stdin.readline

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

b1, b2, b3 = map(int, input().split())
DP = [0 for _ in range(501)]
for i in range(1, 501):
    S = set()
    if i - b1 >= 0:
        S.add(DP[i-b1])
        if i - b2 >= 0:
            S.add(DP[i-b2])
            if i - b3 >= 0:
                S.add(DP[i-b3])
                DP[i] = mex(S)
            else:
                DP[i] = mex(S)
        else:
            DP[i] = mex(S)
    else:
        DP[i] = 0
for _ in range(5):
    k1, k2 = map(int, input().split())
    if DP[k1]^DP[k2] > 0:
        print('A')
    else:
        print('B')