시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 739 | 414 | 349 | 62.883% |
N개의 꼭짓점으로 이루어진 볼록 다각형이 있다. 다각형의 내각은 모두 180보다 작다. 꼭짓점은 1부터 N번까지 시계 방향으로 번호가 매겨져 있다.
성관이와 홍준이는 다각형에서 게임을 하려고 한다. 성관이가 먼저 턴을 갖는다.
각 턴마다 플레이어는 두 꼭짓점을 고르고, 선분을 긋는다 (변과 일치해도 된다). 이때, 이미 그려져 있는 선분과 교차하면 안 된다 (선분의 끝 점에서 겹치는 것도 교차하는 것이다). 더 이상 선분을 그릴 수 없는 사람이 게임을 패배한다.
N이 주어진다. 두 사람이 최적의 방법으로 게임했을 때, 누가 이기는지 구하는 프로그램을 작성하시오.
첫째 줄에 N (3 ≤ N ≤ 1,000) 이 주어진다.
성관이가 이기면 1, 홍준이가 이기면 2를 출력한다.
3
1
4
1
15
2
191
2