ascode.org discuss3

문제 설명

하노이 탑은 팩토리얼을 구하는 함수와 함께 재귀함수를 학습할 떄 주로 사용되는 유명한 예제이다.

"고대 인도 베나레스에 있는 한 사원의 이야기"
여기에는 다이아몬드로 이루어진 3개의 기둥이 있고, 그 기둥 중 하나에 가운데에 구멍이 나 기둥에 끼울 수 있게 된 63개(혹은 64개)의 크기가 각각 다른 황금 원반이 꽂혀 있다고 한다. 황금 원반은 가장 아래쪽에 있는 것이 가장 크고 위로 갈수록 점차 작아져 전체적으로 원추형의 탑을 이루고 있는데, 원반은 한번에 하나씩만 옮길 수 있으며 작은 원반 위에 그보다 더 큰 원반을 옮길 수 없다.
이 규칙으로 63(64)개의 원판을 처음 놓여있던 막대에서 다른 막대로 모두 옮기면 탑은 무너지고 세상의 종말이 온다고 한다.

조건을 정리하자면 아래와 같다.

- 아래 -

한번에 하나의 원판만 이동할 수 있다.
맨 위에 있는 원판만 이동할 수 있다.
크기가 작은 원판 위에 큰 원판이 쌓일 수 없다.
중간의 막대를 임시적으로 이용할 수 있으나 앞의 조건들을 지켜야한다.

위의 조건을 지키며 최소의 이동을 하였을 떄 몇 번을 이동시켜야 하는지 알아보자.

입력 설명

첫줄에 testCase의 수 T(<10)가 입력된다.

이후 T만큼 옮겨야 할 원판의 갯수 N(<=15)가 주어진다.

출력 설명

원판들을 다른 막대로 옮기는데 필요한 최소의 이동 횟수와 방법을 출력한다.

입력 예시 Copy

2
3
4

출력 예시 Copy

원판 1을 A 에서 C로 옮긴다
원판 2를 A 에서 B로 옮긴다
원판 1을 C 에서 B로 옮긴다
원판 3를 A 에서 C로 옮긴다
원판 1을 B 에서 A로 옮긴다
원판 2를 B 에서 C로 옮긴다
원판 1을 A 에서 C로 옮긴다
7
원판 1을 A 에서 B로 옮긴다
원판 2를 A 에서 C로 옮긴다
원판 1을 B 에서 C로 옮긴다
원판 3를 A 에서 B로 옮긴다
원판 1을 C 에서 A로 옮긴다
원판 2를 C 에서 B로 옮긴다
원판 1을 A 에서 B로 옮긴다
원판 4를 A 에서 C로 옮긴다
원판 1을 B 에서 C로 옮긴다
원판 2를 B 에서 A로 옮긴다
원판 1을 C 에서 A로 옮긴다
원판 3를 B 에서 C로 옮긴다
원판 1을 A 에서 B로 옮긴다
원판 2를 A 에서 C로 옮긴다
원판 1을 B 에서 C로 옮긴다
15

도움

자료는 많지만... 한번 직접 풀어보는 것도 좋은 경험이 된다.

Idea.
n개의 원판이 있을 때 n-1개의 원판을 다른 곳으로 옮긴후 가장 아래의 원판을 나머지 하나에 옮긴다.
이후 n-1개를 다시 그 위로 옮긴다.

출처/분류

재귀호출 tomorrow9913