테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 다각형 게임 ======

===== 풀이 =====
  * 여러개의 게임을 동시에 진행하는 형태가 아닌것 같아 보이지만, 선을 긋는 행위를 두개의 다각형으로 나누는 것으로 생각할수 있다. 그래서 [[ps:스프라그-그런디 정리]]를 적용할수 있는 문제가 된다.
  * 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)을 구할수 있다.
    * <del>다른사람의 코드를 보고서 n이 15 또는 35이거나, n%34가 5,9,21,25,29 중 하나일때, g(n)이 0이 된다는 규칙을 알게 되었다. 이 식을 이용하면 O(1)에도 풀리긴 하겠다.. 그러나 어떻게 저렇게 되는지는 전혀 모르겠다</del>
    * 사실 이 게임은 [[ps:스프라그-그런디 정리#Octal Game]] 중 Dawson's Kayle 과 동일한 게임이고, 이 게임은 그런디수가 34의 주기를 갖는다는 것이 잘 알려져 있어서, 그 사실을 이용하면 O(1)에 푸는것도 가능하다.
      * [[ps:problems:boj:16187]]도 동일한 게임이고, 여기에서는 그런디수의 주기성을 이용해서 풀었다.

===== 코드 =====
<dkpr py>
"""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()
</dkpr>

{{tag>BOJ ps:problems:boj:플래티넘_3}}