촘프 게임
시간 제한1초메모리 제한1024 MB
3×N 초콜릿 판에서 두 사람이 챔프 게임을 할 때, 최선의 플레이에서 이기는 쪽과 전체 턴 수를 구하며, 후수가 이기면 음수로 출력한다.
문제
촘프 게임은 두 명이 즐기는 게임이다. 이 게임은 세로 크기가 3, 가로 크기가 N인 나무 판을 사용한다. 나무 판은 크기가 1×1인 칸으로 나누어져 있고, 위에서부터 1번 행, 왼쪽부터 1번 열이다. (x, y)는 x행 y열 칸의 좌표를 의미한다.
처음에는 모든 칸에 공이 하나씩 들어 있다. 두 사람은 턴을 번갈아 가면서 나무판 위의 칸 하나를 선택한다. 선택한 칸의 좌표를 (r, c)라고 할 때, r행보다 크거나 같고 c열보다 크거나 같은 모든 칸에 있는 공을 게임에서 제외한다. (1, 1)에 있는 공을 제외하는 사람이 게임에서 진다.
예를 들어, N = 5인 게임판의 상태가 다음과 같다고 하자. 가장 왼쪽과 위의 정수는 행과 열의 번호이다.
12345
1 XXXXX
2 XXXX
3 XX
여기서 (1, 4)를 고르면 게임판의 상태는 다음과 같이 변한다.
12345
1 XXX
2 XXX
3 XX
여기서 다시 (2, 1)을 고르면 게임판의 상태는 다음과 같아진다.
12345
1 XXX
2
3
두 사람이 최적의 방법으로 게임을 했을 때 누가 이기고, 총 몇 번의 턴이 있었는지 구해 보자. 마지막 (1, 1)에 있는 공을 제외하는 턴이 마지막 턴이고, 턴의 수는 각 사람이 가진 턴 수의 합과 같다. 이길 사람은 최대한 빨리 이기려 하고, 질 사람은 게임을 최대한 오래 지속하려 하는 것이 최적의 방법이다.
입력
첫째 줄에 N이 주어진다.
출력
첫 턴을 갖는 플레이어가 이기는 경우 턴의 수를 출력하고, 두 번째 턴을 갖는 플레이어가 이기는 경우 턴의 수에 -1을 곱해 출력한다.
제한
- 1 ≤ N ≤ 100