문제
서로 다른 N개의 원판과 3개의 기둥이 주어지는 하노이 탑 문제의 일반적인 규칙은 다음과 같다.
규칙1) 한 번에 하나의 원판만 이동시킨다.
규칙2) 작은 원판위에 큰 원판을 놓을 수 없다.
정올이가 하노이탑 블럭을 이용하여 위 규칙에 따라 원판을 이동하며 놀다가 그대로 두었다.
며칠 뒤 그 상태의 블럭을 다시 움직여 K번 기둥에 모든 원판을 모으려고 한다.( 1 <= K <= 3)
최소 이동 수는 어떻게 될까?
이때 이동 과정은 어떻게 될까?
예를 들어 아래 왼쪽 그림과 같은 상태의 하노이 블럭을 오른쪽 그림과 같은 상태로 만들기 위해서는
6번의 이동이 있어야 한다.
입력
첫 행에 원판의 개수 N과 목적 기둥번호 K가 입력된다. ( 1 <= N <= 100,000) ( 1 <= K <= 3)
두 번재 행부터 차례로 1번, 2번, 3번 기둥의 정보가 행으로 구분하여 입력된다.
각 기둥 정보의 첫 수는 기둥에 놓인 원판의 개수 Bi이다.
이어서 기둥에 쌓인 Bi개의 원판번호가 오름차순으로 주어진다. (1 <= Bi <=N)
입력 방법은 입력 예를 참고한다.
출력
첫 행에 이동수 cnt를 10억7로 남은 나머지를 출력한다.
만약 순수한 cnt값이 65536 이하라면 두 번째 행부터 cnt개의 행에 원판의 이동과정을 출력한다.
출력 방법은 출력 예를 참고한다.
예제 #1
3 2
2 1 3
1 2
0
6
2 : 2 -> 3
1 : 1 -> 3
3 : 1 -> 2
1 : 3 -> 1
2 : 3 -> 2
1 : 1 -> 2
예제 #2
4 3
3 1 2 3
0
1 4
7
1 : 1 -> 3
2 : 1 -> 2
1 : 3 -> 2
3 : 1 -> 3
1 : 2 -> 1
2 : 2 -> 3
1 : 1 -> 3
예제 #3
21 1
7 1 2 3 4 5 6 7
8 14 15 16 17 18 19 20 21
6 8 9 10 11 12 13
2097024
출처
comkiwer
로그인해야 코드를 작성할 수 있어요.