[Python] 31687번 Trokut

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

---

 

24/05/18

 

 

스프라그-그런디 정리 문제이다. 약간 웰노운 성이 있는 것 같아서, 정리해보면 좋을 것 같아 글을 써본다.

---

 

문제 접근 방식:

 

 

문제의 접근 방식은 이전에 내가 글로 작성했던 다각형 게임과 동일하다. 심지어, 해당되는 게임조차 같다. 근데 다각형 게임의 코드를 그대로 복붙하면 시간초과를 받는다.

2022.11.01 - [알고리즘/백준 문제 풀이] - [Python] 13034번 다각형 게임 / 16187번 Game on Plane

[Python] 13034번 다각형 게임 / 16187번 Game on Plane

 

$N$의 제한이 $10^9$으로 크기 때문이다.

 

그래서 규칙을 발견해서 접근해야 된다.

 

여기서 웰노운이라면 웰노운일 수 있는 마법의 숫자 "34"가 등장한다. 이 게임은 34를 주기로 하여 님버가 반복이 된다.

 

잊힐만하면 등장하는 수상한 숫자인데, 사실은 이러한 게임이 특정 게임 군(Octal game)에 속하기 때문이다.

 

https://en.wikipedia.org/wiki/Octal_game

Octal game - Wikipedia

https://www.teferi.net/ps/%EC%8A%A4%ED%94%84%EB%9D%BC%EA%B7%B8-%EA%B7%B8%EB%9F%B0%EB%94%94_%EC%A0%95%EB%A6%AC

스프라그-그런디 정리 [테페리넷]

이에 대한 정보는 위의 블로그에서 얻었다.

 

이 게임은 Octal game에 속하고, Octal game의 대부분은 주기를 가지고 있다. 특히, 그 중 몇 개는 34를 주기로 가지는데, 이 게임 또한 그러한 분류 중 하나에 속하기 때문에 34를 주기로 가진다.

 

자세한 증명은 아래 글을 참고해보자. 이 글은 주기가 반복되는 것 같다면, 그 주기가 실제로 무한히 반복되는 것이 맞다는 사실을 증명하는 정리이다.

 

https://combinatorialgames.wordpress.com/2012/08/10/i-7-a-strategy-for-kayles-guy-smith-periodicity/

I.7: A Strategy for Kayles (Guy-Smith Periodicity)

 

아마 이 문제의 풀이 방식과 유사하게 풀리는 문제들도 몇 개 있었던 걸로 아는데, 이전의 다각형 게임도 그렇고, 초콜릿 쪼개기 게임도 그러하다.

 

똑같이 주기 34를 가지고 있으며, 아마 그런디 수도 유사했던 것으로 기억난다.

 

---

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

# 31687번 Trokut
# 스그
'''
접근 방법:
34
'''
import sys
input = sys.stdin.readline

DP = [0, 0, 1, 1, 2, 0, 3, 1, 1, 0, 3, 3, 2, 2, 4, 0, 5, 2, 2, 3, 3, 0, 1, 1, 3, 0, 2, 1, 1, 0, 4, 5, 2, 7,
4, 0, 1, 1, 2, 0, 3, 1, 1, 0, 3, 3, 2, 2, 4, 4, 5, 5, 2, 3, 3, 0, 1, 1, 3, 0, 2, 1, 1, 0, 4, 5, 3, 7,
4, 8, 1, 1, 2, 0, 3, 1, 1, 0, 3, 3, 2, 2, 4, 4, 5, 5, 9, 3, 3, 0, 1, 1, 3, 0, 2, 1, 1, 0, 4, 5, 3, 7]

T = int(input())
for _ in range(T):
    N = int(input())
    if N >= 68:
        N = N%34 + 68
    print('Lucija' if DP[N] else 'Ivan')