[Python] 32299번 게임을 만들어요

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

---

 

24/11/10

 

 

전형적인 게임이론 문제다.

---

 

문제 접근 방식:

 

 

$N=3$인 경우를 제외하면 항상 후공이 이긴다.

 

그 이유는 게임 판을 도넛 모양으로 분리하면, 한 도넛에서 다른 도넛으로 움직일 때마다 선공과 후공의 유리한 정도가 달라지는데, 다른 도넛으로 움직일 때 후공이 유리하다면 후공은 그냥 그 방향으로 움직이면 되고, 다른 도넛으로 움직일 때 선공이 유리하다면, 후공이 현재 도넛에서 빙빙 돌면서 선공이 다른 도넛으로 넘어가도록 만들 수 있기 때문이다.

 

게임이론에서 자주 나오는 테크닉인데, 핵심은 후공이 항상 선공이 불리하도록 게임판을 "조정"할 수 있다는 것이 핵심이다. 

---

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

# 32299번 게임을 만들어요
N = int(input())
if N == 3:
    print('Hobanwoo')
else:
    print('Sangho')