====== 결함 게임 ======

===== 풀이 =====
  * 우선 돌을 더 올릴수 있는 돌탑을 활성화된 탑이라고 부르자. 활성화된 탑이 있을 때는 새로운 탑을 만들수 없으므로, 게임중의 어떤 상태에서도 활성화된 탑의 갯수는 1개 또는 0개만 있을수 있다.
  * 선공과 후공에 관계 없이 확실히 승리 포지션은, 남아있는 돌이 2개이고 활성화된 탑이 없는 상태이다. 이 상태에서 작은 돌로 탑을 만들면 최종적으로는 탑이 두개 더 추가되고, 큰 돌로 탑을 만들면 탑이 한개 추가된다. 따라서 원하는 대로 탑의 총 갯수를 홀수가 되게 할수도 있고 짝수가 되게 할수도 있다.
  * 다른 승리포지션은 활성화된 탑이 없고, 남아있는 돌이 1개이고, 이제부터 탑을 1개만 더 만들어야 하는 상황이다. 어차피 선택지가 1가지뿐이지만, 그 행동이 승리조건이 된다.
  * 이제 내게 돌아오는 다음 포지션을 강제하는 방법을 생각해보자. 활성화된 탑이 없고 N개의 돌이 있는 상태에서, 2번째로 작은 돌로 새 탑을 만든다면, 상대방은 가장작은 돌을 그 탑위에 올리는 것밖에 할수 없다. 그리고 나면 다시 내게는 활성화된 탑이 없고, N-2개의 돌이 있는 포지션이 돌아온다.
  * 처음 시작할때 N이 짝수개라면, 선공은 이 전략을 반복해서 돌이 N-2, N-4, ...개 있는 포지션을 계속 차지할수 있다. 그리고 돌이 2개 남은 포지션에 오면 거기서 현재까지 만들어진 탑의 갯수에 따라 전략을 결정하면 되므로 선공이 항상 이길수 있다.
  * 처음 시작할때 N이 홀수개라면, 이 전략을 반복해서 돌이 1개 있는 포지션까지 가져갈수는 있다. 이때까지 만들어진 탑의 갯수가 짝수개라면, 마지막 돌로 탑을 하나 추가해서 이길수 있다. N%4=1 인 경우에는 이 방법으로 이길수 있다.
  * N%4=3 인 경우에는, 2번째로 작은 돌로 새 탑을 만드는 것을 반복하는 것으로 이길수는 없다. 다른 방법으로 이길수 있는 전략이 있는지 생각해보자. 
    * 가장 작은 돌로 새 탑을 만드는 방법을 생각하자. 그것은 상대에게 활성화된 탑이 없으면서 남아있는 돌이 짝수개인 포지션을 넘겨주는 것이다. 그리고 그러한 포지션은 선공에게도 후공에게도 승리포지션이므로, 결국 상대방이 이기게 된다.
    * k번째 작은 돌 (k>2) 로 새 탑을 만드는 방법을 생각하자. 상대는 활성화된 탑과 짝수개의 돌이 있는 포지션을 받고, 탑 위에 올릴수 있는 돌의 갯수는 2개 이상이다. 이제 두번째로 작은 돌을 활성화된 탑 위에 올려서 내게 넘겨주면 나는 가장 작은 돌을 탑 위에 올리는것 외에 선택지가 없다. 이 과정을 거치면 역시 상대는 활성화된 탑이 없으면서 남아있는 돌이 짝수개인 포지션을 받게 되고, 승리할수 있다.
    * 결국, N%4=3 인 경우에는 항상 후공에게 필승 전략이 있다.
  * 정리하면, 선공이 승리할수 있는 처음 포지션은 N%4가 1,2,4 중 하나이면 된다.


===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 17080. 결함 게임".

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

Tags: [game theory]
"""


def main():
    N = int(input())
    print('1' if N % 4 != 3 else '2')


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

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