하노이3(4기둥) > 문제은행



1405 : 하노이3(4기둥)

제한시간
1000 ms   
메모리제한
32 MB   
해결횟수
146 회   
시도횟수
545 회   

문제

전설의 하노이 탑 문제는 기둥이 3개이다.

 

기둥이 4개인 경우의 문제는 어떻게 될까?

기둥 번호는 차례로 A, B, C, D이고 N개의 원판을 A번 기둥에서 D번 기둥으로 옮겨야 한다.

 

3288문제에서는 이동하는 최소 횟수만 출력하였지만 그 과정도 출력해보자.

 

규칙은 3288 문제와 같다.

조건 1) 한 번에 하나의 원판만 옮길 수 있다.

조건 2) 반드시 큰 원판 위에 작은 원판이 있어야 한다. 

조건 3) 각 탑의 맨 위에 있는 원판만 옮길 수 있다. 

 

 

 

 


입력형식

첫 줄에 한 정수 n이 입력된다. (단, 1 <= n <= 20 )

출력형식

첫 번째 줄에 4개의 기둥을 이용하여 옮기는 횟수를 출력한다.

두 번째 줄부터 각 원판을 옮기는 경로를 다음과 같이 출력한다. 

 

원판번호 : 원판이 있던 기둥번호 -> 원판이 이동한 기둥번호 

 

규칙을 지키는 경로가 여러 개라면 아무거나 출력해도 된다.


입력 예

2

출력 예

3
1 : A->B
2 : A->D
1 : B->D

Hint!

참고 : wiki


출처

comkiwer

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010-2019 jungol. All right reserved.

TOP