1645 : 도미노 밟기 (TOTEM)
- 제한시간
- 1000 ms
- 메모리제한
- 32 MB
- 해결횟수
- 0 회
- 시도횟수
- 3 회
문제
미르코는 N2-[N/2] (단, [x]는 x의 정수부분) 개의 도미노를 가지고 도미노 밟기 놀이를 하려고 한다.
먼저, N행에 도미노를 나열하는데, 짝수 행에 N-1개의 도미노를 일렬로 배열하고, 홀수 행에는 N개의 도미노를 일렬로 배열한다.
N=5인 경우 다음과 같은 형태로 도미노를 배열하게 된다.
미르코는 각 도미노에 1~N2-[N/2] 의 번호를 행이 작은 순서대로 왼쪽에서부터 오른쪽 방향으로 붙이게 된다.
위 그림에서는 7번 도미노는 2행에 있는 (5,6)이 쓰여 있는 도미노이고, 15번 도미노는 4행에 있는 (4,2)가 쓰여 있는 도미노와 같다.
미르코는 1번 도미노에서부터 시작해 여러 도미노들을 밟고 간다.
미르코가 한 도미노를 밟았을 때, 그 도미노와 한 모서리를 공유하면서 그 모서리 양 끝의 두 수가 같은 도미노만 밟을 수 있다.
1번 도미노와 2번 도미노는 한 모서리를 공유하면서 그 모서리 양 끝의 두 수가 4로 같기 때문에 1번 도미노를 밟고 연달아 2번 도미노를 밟을 수 있다.
반면 2번 도미노와 3번 도미노는 한 모서리를 공유하지만
그 모서리 양 끝의 두 수가 5, 3으로 다르기 때문에 2번 도미노를 밟고 연달아 3번 도미노를 밟을 수 없다.
도미노 밟기 놀이의 목적은 보다 빨리 번호가 큰 도미노를 밟는 것이다.
미르코를 도와 도달할 수 있는 가장 큰 도미노로 가기 위해 밟아야 하는 최소 도미노 수와 그 때의 도미노 번호를 구하는 프로그램을 작성하여라.
입력형식
출력형식
입력 예5 1 4 4 5 3 4 5 4 5 2 4 2 5 6 4 4 6 5 2 4 5 1 6 1 1 6 2 3 4 2 5 3 1 2 5 5 4 1 2 2 4 3 2 3 3 4 |
출력 예7 1 2 7 12 17 22 23 |
입력 예3 1 2 2 3 6 6 2 4 3 5 6 6 4 5 5 6 |
출력 예4 1 2 5 8 |
입력 예4 1 5 5 3 5 5 5 6 5 3 6 4 4 5 2 5 2 4 4 3 2 4 5 2 1 4 1 6 |
출력 예7 1 5 8 12 9 10 13 |