[재귀] 하노이 탑
2021. 5. 30. 23:12ㆍ백준
11729번: 하노이 탑 이동 순서
세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로
www.acmicpc.net
첫 공부를 할 시점에 이 문제를 접했던 기억이 난다.
아무리 생각해도 모르겠어서 이 길이 내 길이 아닌지 심각하게 고민했던 시기가 있었는데...
지금에는 보고 쉽게 풀지만 그 당시에는 정말 내 앞을 가로막은 거대한 벽으로 느껴졌었다.
count = int(input())
def move(now, target, empty, c):
if c == 1:
print(now, target)
return
move(now, empty, target, c - 1)
print(now, target)
move(empty, target, now, c - 1)
print((2 ** count) - 1)
move(1, 3, 2, count)