도미노 밟기 (TOTEM) > 문제은행



실전대비 Level7

1645 : 도미노 밟기 (TOTEM)

제한시간: 1000 ms    메모리제한: 32 MB
해결횟수: 11 회    시도횟수: 60 회    Special Judge



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

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

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

 

 

07f1ee470c4ca420b78cf86b19196679_1450334
 

 

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

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

 

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

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

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

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

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

 

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

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

 




첫 번째 줄에는 도미노 놀이 게임판의 크기 N이 주어진다. (1 ≤ N ≤ 500)
두 번째 줄부터 1~N2-[N/2]개의 줄에는 각 도미노에 써져 있는 6 이하의 두 자연수(왼쪽 수가 먼저 입력됨)가 주어진다.



첫 번째 줄에는 도달할 수 있는 가장 큰 도미노로 가기 위해 밟아야 하는 최소 도미노 수를 출력한다.
두 번째 줄에는 그 때 밟는 도미노의 번호를 출력한다.
답이 여러 개이면 그 중 하나만 출력한다.


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






HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 031-388-0999 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.