테페리넷

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

===== 풀이 =====
  * {{ps:kupc2025.pdf|에디토리얼}}에서는 강제수를 따라가면서 관찰하면 4칸마다 같은 패턴이 반복된다고 간단하게 설명하고 있다.
  * 좀 더 구체적으로 따져보자. 오른쪽으로 1칸 이동을 +1로 표기하자. 선공의 첫수는 좌우대칭이므로 그냥 +1로 간주하면, 후공은 -2와 +2 둘중 하나를 선택할수 있다. 
  * 여기서 후공이 -2를 선택하면, A칸 그리드의 오른쪽 끝에 돌이 놓여있고, 선공이 움직일 차례인 상태가 된다.   
    * A=1이면 선공이 움직일 수 없으니 후공 승리
    * A=2이면 선공의 -1 이후 후공이 움직일수 없으니 선공 승리
    * A=3이면 선공의 -1 이후 후공이 움직일수 없으니 선공 승리
    * A=4이면 선공의 -1 -> 후공 -2 -> 선공 +1 이후 움직일수 없으니 선공 승리
    * A=5이상이면, 선공 -1 -> 후공 -2 -> 선공 +1 -> 후공 -2 까지 강제수이고, 이 이후, (A-4)칸 그리드의 오른쪽 끝에 돌이 놓여있는 상태로 돌아온다.
      * 선공 -1 -> 후공 -2 이후에 선공이 -1을 고르는 것은 불가능하다. 후공이 바로 +2를 해서 후공 승리로 끝나기 때문
    * 즉, N칸 그리드의 한쪽 끝에 돌이 있는 상황에서는 N % 4 ==1 일때만 후공이 이긴다. 
  * 처음에 후공이 +2를 선택하면, 그다음 선공은 -1, 후공은 +2를 선택하는 것까지가 강제수이다. 이렇게 되면 (A-3)칸 그리드의 한쪽 끝에 돌이 놓여있는 상태가 된다.
  * 정리하면, 게임이 진행되면 항상 X칸 그리드의 한쪽 끝에 돌이 놓여져 있는 상태가 된다. 이때 X%4==1 이면 후공이 승리하고, 후공은 X를 A 또는 A-3 중 하나로 정할수가 있다. 그러므로 A%4 가 1 이거나 0 이면 후공이 이길수 있다.


===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 34764. 고양이 게임".

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

Tags: [game theory]
"""


def main():
    N = int(input())
    print('goose' if N % 4 <= 1 else 'duck')


if __name__ == '__main__':
    main()
</dkpr>


{{tag>BOJ ps:problems:boj:골드_4}}