[Python] 백준 18490 - 숫자 카드 제거 게임

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

풀이

먼저 지난번에 올린 스프라그-그런디 정리(이하 스그정리)에 관한 글을 읽어보고 오면 도움이 많이 된다.

 

13034번 문제와 비슷하다.

먼저 N = 0일때는 그룬디 수가 0(패배상태이므로)

N = 1, 2일때는 그룬디 수가 1이다. 단 한번의 행동으로 무조건 패배상태로 만들 수 있으므로 이 경우는 마음대로 그룬디 수를 1로 잡아도 좋다.

 

N이 3 이상일때는, 어떤 임의의 부분에서 연속된 최대 3개의 카드를 제거함으로 인해 보드판이 두 개로 나뉜다.

가령 다음과 같다.

N = 6일때

N = 6일때 3을 골랐다고 해보자. 이제 보드판은 (1) 부분과 (5, 6) 부분 두 개로 나누어졌다. 이 상태는 grundy[1]과 grundy[2]의 님 합으로 표현할 수 있다.

이렇게 여섯 가지의 보드판이 나누어지는 경우에 대해서 mex 함수를 적용해주면 최종적으로 grundy[6]을 구할 수 있다.

 

이런 식으로 계속 구해주면 되는데....문제가 있다. N의 범위가 오백만이다.

import sys
input = sys.stdin.readline
T = int(input())
hoobo = []
for _ in range(T):
    hoobo.append(int(input()))
grundy = [0, 1, 1]
for i in range(3, max(hoobo)+1):
    tmp = set()
    for j in range(-1, i-1):
        a = max(0, j)
        b = max(0, i-3-j)
        tmp.add(grundy[a]^grundy[b])
    for mex in range(1000000):
        if mex not in tmp:
            grundy.append(mex)
            break
print(grundy)
for i in range(len(grundy)):
    if not grundy[i]:
        print(i)
for i in hoobo:
    if grundy[i] > 0:
        print('Yuto')
    else:
        print('Platina')

 

그래서 위 코드를 제출하면 시간복잡도가 O(N^2)가 되어 TLE를 받는다.

이걸 O(N)에 계산을 어떻게 할까?

보통 스그정리를 쓰는 문제에서 이런 경우에는 그룬디 수에 규칙이 있을 가능성이 크다!

어떤 경우에 패배상태인지 출력해보고 규칙을 찾아보자.

 

 

파란색으로 인접한 두 수의 차이를 적어보면, 42 이후로부터 +12, +4, +4, +10, +4가 반복됨을 알 수 있다.

이를 통해서 미리 모든 그룬디 수를 구해놓고 AC를 받을 수 있다.

 

import sys
input = sys.stdin.readline
ans = [True]*(5_000_001)
for i in [0, 4, 8, 14, 20, 24, 28, 34, 38, 42]:
    ans[i] = False
idx = 42
while idx < 5_000_001:
    for a in [12, 4, 4, 10, 4]:
        idx += a
        if idx < 5_000_001:
            ans[idx] = False
for i in range(int(input())):
    N = int(input())
    if ans[N]:
        print('Yuto')
    else:
        print('Platina')