백준 11729 하노이 탑 이동 순서 (파이썬)
재귀의 근본..하노이탑…
직접 해보라고 하면 할 수 있는 있는데 알고리즘으로 짜기가 어려웠다.
학부에서 처음 재귀 배울 때 사용했던 프린트자료를 찾았는데 교수님이 그림까지 그려서 설명해준 자료가 남아서 웃기면서도 아직까지 자료없이는 헤맨다는 사실이 슬펐다…ㅋㅋ
이번 기회에 꼭 머리에 넣어둬야지!
접근방식
- n-1개의 원판을 A에서 B로 옮기고
- n번째 원판을 A에서 C로 옮긴 다음
- n-1개의 원판을 B에서 C로 옮긴다.
파이썬 코드
n = int(input())
def hanoi(n,a,b,c):
if n == 1:
print(a,c)
else:
hanoi(n-1,a,c,b)
print(a,c)
hanoi(n-1,b,a,c)
total = 1
for i in range(n-1):
total = total * 2 + 1
print(total)
hanoi(n,1,2,3)
