https://jungol.co.kr/problem/1749
| 시간 제한 | 메모리 제한 |
| 1초 | 128MB |
문제
두 사람 A와 B가 번갈아 가면서 두 개의 구슬 통에서 몇 개씩의 구슬을 꺼내는 게임을 한다.
한번에 한 사람이 한 통에서 꺼낼 수 있는 구슬의 개수는 세 가지 뿐이다.
그리고 구슬을 꺼낼 경우 두 개의 구슬 통 중에서 하나를 마음대로 선택해서 그 안에서만 꺼낼 수 있다.
즉 두 개의 통 모두에서 동시에 몇 개씩 꺼낼 수는 없다.
게임은 항상 A가 먼저하고 그 다음 B, 그 다음 A 순으로 번갈아가면서 진행된다.
그리고 자신의 차례 가 되었을 때에 정해진 규칙대로 구슬을 꺼낼 수 없는 사람이 게임에서 지게 되고, 상대방은 승리하게 된다.
예를 들어 한번에 꺼낼 수 있는 구슬의 개수를 1개, 3개, 또는 4개라고 하자.
만일 두 개의 구슬 통 에 각각 4개, 1개의 구슬이 있다고 하면 처음 선택을 하게 되는 A가 이긴다.
그러나 만일 두 통속의 구슬이 각각 5개, 5개라면 B가 이긴다.
즉 한번에 꺼낼 수 있는 구슬 개수인 b1 , b2 , b3가 주어지고,
두 구슬 통 속에 들어있는 구슬의 수 인 k1, k2이 정해지면,
이러한 b1 , b2 , b3와 k1, k2에 따라서 승패는 결정된다.
문제는 주어진 b1, b2 , b3와 k1, k2에 대하여 A, B중 누가 승자인지를 결정하는 것이다.
처음 두 통 속에 들어 있는 구슬의 수 k1, k2와 한 번에 꺼낼 수 있는 구슬의 수 b1 , b2 , b3에 대한 제한조건은 다음과 같다.
$1 \leq b1 < b2 < b3 \leq 30$
$1 \leq k1, k2 \leq 500$
입력
첫 줄에는 한번에 꺼낼 수 있는 구슬의 개수를 나타내는 세 개 의 정수 b1 , b2, b3 가 나타난다.
그 다음 5개의 각 줄에는 두 통속에 처음 담겨있는 구슬의 개수 k1, k2가 각각 표시되어 있다.
출력
여러분은 입력파일에 표시된 각 5개의 k1 , k2 경우에 대하 여 그에 대응되는 승자(A 또는 B)를 각각 한 줄에 하나씩 차례대로 다섯 개를 출력해야 한다.
풀이
스프라그-그런디 정리로 쉽게 해결 가능하다.
두 더미 k1과 k2에 대해 남은 구슬의 수 x에 대한 그런디 수 `g(x)`를 모두 구해버리면 됩니다. 구슬의 개수는 최대 500개 이므로 주어지는 b1, b2, b3를 가지고 0~500 범위의 `g(x)`를 미리 구해서 xor 연산으로 두 더미가 주어졌을 때 승패를 알 수 있습니다.
`g(x)`는 이전(아니 다음이라고 해야 하나?) 상태(x-b1, x-b2, x-b3)를 모두 합쳤을 때 mex로 구할 수 있습니다.
B = list(map(int, input().split())
g = [0] * 501
for i in range(B[0], 501):
# B[0]보다 작은 상태는 모두 패배 상태임: g(x) = 0
state = set()
for b in B:
if b > i: break # i - b < 0 인 상태는 존재할 수 없음
state.add(g[i-b]) # state에 이전 상태의 mex를 모두 합치기
for j in range(4): # b1, b2, b3 밖에 없으므로 mex는 0~3까지만 가능함
if not(j in state):
g[i] = j
break
`g(x)`가 0인 경우는 패배 상태이므로 B가 승리, 아닌 경우는 A가 승리합니다.
정답 코드
def solution():
B = list(map(int, input().split()))
grundy = [0] * 501
for i in range(B[0], 501):
link = set()
for b in B:
if b > i: break
link.add(grundy[i-b])
for j in range(4):
if not(j in link):
grundy[i] = j
break
for _ in range(5):
p, q = map(int, input().split())
if grundy[p] ^ grundy[q]: print('A')
else: print('B')
solution()
