미르코는 N²-[N/2] (단, [x]는 x의 정수부분) 개의 도미노를 가지고 도미노 밟기 놀이를 하려고 한다.

먼저, N행에 도미노를 나열하는데, 짝수 행에 N-1개의 도미노를 일렬로 배열하고, 홀수 행에는 N개의 도미노를 일렬로 배열한다.

N=5인 경우 다음과 같은 형태로 도미노를 배열하게 된다.

미르코는 각 도미노에 1~N²-[N/2] 의 번호를 행이 작은 순서대로 왼쪽에서부터 오른쪽 방향으로 붙이게 된다.

위 그림에서는 7번 도미노는 2행에 있는 (5,6)이 쓰여 있는 도미노이고, 15번 도미노는 4행에 있는 (4,2)가 쓰여 있는 도미노와 같다.

미르코는 1번 도미노에서부터 시작해 여러 도미노들을 밟고 간다.

미르코가 한 도미노를 밟았을 때, 그 도미노와 한 모서리를 공유하면서 그 모서리 양 끝의 두 수가 같은 도미노만 밟을 수 있다.

1번 도미노와 2번 도미노는 한 모서리를 공유하면서 그 모서리 양 끝의 두 수가 4로 같기 때문에 1번 도미노를 밟고 연달아 2번 도미노를 밟을 수 있다.

반면 2번 도미노와 3번 도미노는 한 모서리를 공유하지만

그 모서리 양 끝의 두 수가 5, 3으로 다르기 때문에 2번 도미노를 밟고 연달아 3번 도미노를 밟을 수 없다.

도미노 밟기 놀이의 목적은 보다 빨리 번호가 큰 도미노를 밟는 것이다.

미르코를 도와 도달할 수 있는 가장 큰 도미노로 가기 위해 밟아야 하는 최소 도미노 수와 그 때의 도미노 번호를 구하는 프로그램을 작성하여라.

도미노 밟기 (TOTEM) timer 1초 memory 32MB

도미노 밟기 (TOTEM) 1초 32MB