17080번 - 결함 게임

문제

택희와 현우는 게임을 하나 하려 한다. 이 게임은 보드판 하나와 N개의 크기가 서로 다른 돌들을 이용해 진행된다. 게임의 규칙은 아래와 같다.

• ‘돌탑’ 이란, 크기가 가장 큰 돌이 아래, 가장 작은 돌이 위에 오도록 크기 순으로 정렬되어 쌓인 돌무더기를 의미한다.
• 처음엔 크기가 1, 2, …, N인 돌 하나씩과 비어 있는 보드판 하나를 가지고 시작하며, 서로 번갈아가며 보드판에 새로운 돌탑의 바닥을 만들거나 보드판 위에 있는 기존의 돌탑 위에 돌 하나를 올려놓는 식으로 진행된다. 각 크기의 돌은 하나씩밖에 없으며, 두 플레이어가 공유한다. 각 돌은 한번 보드판 위에 올라간 이후엔 아무도 손댈 수 없다.
• 각 플레이어는 턴마다, 만약 현재 보드 위에 있는 돌탑 중 어딘가에 올릴 수 있는 돌이 남아있다면, 반드시 그러한 돌들 중 하나를 골라 올릴 수 있는 돌탑 중 원하는 돌탑 위에 올린다.
• 만약 어떤 돌탑에도 돌을 올릴 수 없다면, 남아있는 돌 중 아무거나 하나를 골라 보드 위에 새로운 돌탑의 바닥을 만든다.
• 모든 돌이 소진된 뒤, 돌탑의 개수가 홀수이면 선공이 이기며, 짝수이면 후공이 이긴다.

택희와 현우는 게임을 하기 위해 N개의 크기가 서로 다른 돌을 모았다. 둘은 항상 최선을 다하며, 이길 수 있는 상황에선 반드시 이긴다고 가정할 때, 이 게임의 승자는 누가 될까?

입력

첫째 줄에 돌의 개수 N이 주어진다. (1 ≤ N ≤ 5,000,000)

출력

선공이 이긴다면 1을, 후공이 이긴다면 2를 출력한다.

제한

힌트