https://www.acmicpc.net/problem/11729
시간 1초, 메모리 256MB
input :
- N (1 ≤ N ≤ 20)
output :
- 옮긴 횟수 K
- 수행 과정을 출력 ( A B 출력 / A번째 탑의 가장 위 원판 -> B번째 탑의 가장 위로 옮긴다)
조건 :
- 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
- 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.
하노이 탑이 움직이는 동작과정.
hanoi(n, from, to)
n개의 원판을 from 기둥에서 to 기둥으로 옮긴다.
재귀의 기저 사례.
가장 위의 원판 1개가 남았을 때 이를 from에서 to기둥으로 옮긴다.
원판들은 언제나 가장 큰 원판 n번 원판을 to 기둥으로 옮겨야하는데 그래서 그 외의 n - 1개의 원판들은 중간의 기둥으로 옮겨져야 한다.
hanoi(n - 1, from, middle)
그러면 중간 기둥을 구하려면 어떻게 하면 되는가?
하노이 탑의 기둥은 3개이다. 1, 2, 3
이 합은 6.
from, to 를 빼주면 middle 기중의 번호를 알 수 있다.
그러면 위의 과정을 해서 나머지 원판들을 중앙에 넣었으니 가장 큰 원판을 to기둥으로 옮긴다.
print("from에서 to로 옮기기")
그 후 hanoi(n - 1, middle, from)으로 옮겨준다.
import sys
n = int(sys.stdin.readline())
result = []
def hanoi(disk, from_, to):
if disk == 1:
result.append((from_, to))
else:
other_poll = 6 - from_ - to
hanoi(disk - 1, from_, other_poll)
result.append((from_, to))
hanoi(disk - 1, other_poll, to)
hanoi(n, 1, 3)
print(len(result))
for item in result:
print(item[0], item[1])그림이 이뻐서 넣어보았다. 나중에 잊어버리면 다시 읽어봐야지...
맨 처음에 3넣고 하노이 탑 만들다가 n으로 안 바꿔줘서 한 번 틀렸다 ㅋㅋㅋㅋㅋㅋㅋㅋ
