사용자 도구

사이트 도구


ps:problems:boj:13034

다각형 게임

ps
링크acmicpc.net/…
출처BOJ
문제 번호13034
문제명다각형 게임
레벨플래티넘 3
분류

스프라그-그런디

시간복잡도O(n^2)
인풋사이즈n<=1000
사용한 언어Python
제출기록30840KB / 112ms
최고기록60ms
해결날짜2022/05/31

풀이

  • 여러개의 게임을 동시에 진행하는 형태가 아닌것 같아 보이지만, 선을 긋는 행위를 두개의 다각형으로 나누는 것으로 생각할수 있다. 그래서 스프라그-그런디 정리를 적용할수 있는 문제가 된다.
  • n각형에 선을 그으면, 선 끝에 해당하는 두개의 꼭지점에서는 더이상 선을 그릴수 없으니까, 결국 i각형과 (n-i-2)각형으로 분리되는 것과 동일하다. g(n) = mex_i{g(i)^g(n-i-2)} 의 식으로 정리할수 있는데, 이렇게 구해지는 g값을 나열해봐도 특별한 패턴을 찾기는 힘들다. 그냥 DP로 g(0)부터 g(n)까지 차례차례 계산하면 O(n^2)에 g(n)을 구할수 있다.
    • 다른사람의 코드를 보고서 n이 15 또는 35이거나, n%34가 5,9,21,25,29 중 하나일때, g(n)이 0이 된다는 규칙을 알게 되었다. 이 식을 이용하면 O(1)에도 풀리긴 하겠다.. 그러나 어떻게 저렇게 되는지는 전혀 모르겠다
    • 사실 이 게임은 Octal Game 중 Dawson's Kayle 과 동일한 게임이고, 이 게임은 그런디수가 34의 주기를 갖는다는 것이 잘 알려져 있어서, 그 사실을 이용하면 O(1)에 푸는것도 가능하다.
      • Game on Plane도 동일한 게임이고, 여기에서는 그런디수의 주기성을 이용해서 풀었다.

코드

"""Solution code for "BOJ 13034. 다각형 게임".

- Problem link: https://www.acmicpc.net/problem/13034
- Solution link: http://www.teferi.net/ps/problems/boj/13034

Tags: [Sprague-Grundy]
"""


def main():
    N = int(input())

    grundy = [0] * (N + 1)
    for i in range(2, N + 1):
        next_grundy_nums = {
            grundy[j] ^ grundy[i - j - 2] for j in range(i // 2)
        }
        grundy[i] = next(x for x in range(N) if x not in next_grundy_nums)

    print('1' if grundy[N] > 0 else '2')


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
V D N Y U
 
ps/problems/boj/13034.txt · 마지막으로 수정됨: 2022/06/07 14:00 저자 teferi