문제
전설의 하노이 탑 문제는 기둥이 3개이다.
기둥이 4개인 경우의 문제는 어떻게 될까?
기둥 번호는 차례로 A, B, C, D이고 N개의 원판을 A번 기둥에서 D번 기둥으로 옮겨야 한다.
3288문제에서는 이동하는 최소 횟수만 출력하였지만 그 과정도 출력해보자.
규칙은 3288 문제와 같다.
조건 1) 한 번에 하나의 원판만 옮길 수 있다.
조건 2) 반드시 큰 원판 위에 작은 원판이 있어야 한다.
조건 3) 각 탑의 맨 위에 있는 원판만 옮길 수 있다.
입력
첫 줄에 한 정수 n이 입력된다. (단, 1 <= n <= 20 )
출력
첫 번째 줄에 4개의 기둥을 이용하여 옮기는 횟수를 출력한다.
두 번째 줄부터 각 원판을 옮기는 경로를 다음과 같이 출력한다.
원판번호 : 원판이 있던 기둥번호 -> 원판이 이동한 기둥번호
규칙을 지키는 경로가 여러 개라면 아무거나 출력해도 된다.
예제1
입력
2
출력
3
1:A->B
2:A->D
1:B->D
힌트
출처
comkiwer