[Python] 5981번 Cow Checkers

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

---

 

24/05/23

 

 

모르면 쳐맞는 종류의 게임 이론 문제인 것 같아서 따로 정리해야겠다, 싶어 정리해본다.

---

 

문제 접근 방식:

 

 

https://en.wikipedia.org/wiki/Wythoff%27s_game

Wythoff's game - Wikipedia

이 게임은 게임 이론에서 잘 알려진 종류의 게임 중 하나로, 체스보드 위에서 퀸이 움직일 때 마지막으로 퀸을 움직인 사람이 승리하는 게임으로 치환할 수 있다.

 

이 문제에서 주어진 상황이 딱 그러한 상황인데, 다행히도 Cold position(선공이 지는 포지션)에 대한 공식이 다음과 같이 잘 나와있다.

 

$$\begin{align}n_k=\lfloor k \phi \rfloor = \lfloor m_k \phi \rfloor - m_k\\m_k = \lfloor k\phi^2 \rfloor = \lceil n_k\phi \rceil = n_k + k \end{align}$$

 

여기서 $\phi$는 황금비로, 정확한 값은 $\frac{1+\sqrt{5}}{2}$로 나타낼 수 있다.

 

위의 공식을 사용하여, $\mathcal{O}(1)$의 시간 복잡도로 이기는지 지는지 판단할 수 있다.

 

왜 저러한 공식이 나오는지에 대한 여부는 위키의 출처를 자세히 읽어보자. 

---

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

# 5981번 Cow Checkers
# 게임이론
'''
접근 방법:
https://en.wikipedia.org/wiki/Wythoff%27s_game
'''
import sys
input = sys.stdin.readline
from math import ceil, floor
from decimal import *
getcontext().prec = 116

M, N = map(int, input().split())
T = int(input())
def wythoff_game(n, m):
    golden_ratio = Decimal('1.618033988749894848204586834365638117720309179805762862135448622705260462818902449707207204189391137484754088075386')
    if n > m:
        n, m = m, n
    k = m-n
    if int(k*golden_ratio) == n and int(k*golden_ratio*golden_ratio) == m:
        return False
    return True
for _ in range(T):
    n, m = map(int, input().split())
    if wythoff_game(n, m):
        print('Bessie')
    else:
        print('Farmer John')