하노이 4 > 문제은행

본문 바로가기


알고리즘 백트랙킹2

1405 : 하노이 4

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



민성이는 요새 하노이 탑 게임에 빠져있다.

사악한 서쌤은 민성이를 괴롭히기 위해 민성이에게 "4개짜리 기둥에 N개의 원판을 최소 이동횟수로 이동시켜라" 라고 시켰다.

거기에다가 어떤 원판을 어느 기둥에서 어느 기둥으로 이동하는지 역시 모두 출력하라고 시켰다.

 

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

민성이의 가장 친한 친구인 당신이 민성이를 도와주자! 

 

82de47fbe69017d305c733b84f0a7e8e_1457341 


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


첫 번째 줄에 4개의 기둥을 이용하여 옮기는 횟수를 출력한다.
두 번째 줄부터 각 원판을 옮기는 경로를 다음과 같이 출력한다.

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

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

[Copy]
2
[Copy]
3
1 : A->B
2 : A->D
1 : B->D


출처 : jungol



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