[백준] 11729번: 하노이의 탑 이동 순서 - python

https://www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

 

정답:

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)

n=int(input())
print(2**n-1) # 이동 횟수 
hanoi(n,1,2,3)

 

풀이:

 

먼저 n-1개를 C를 이용해서 B로 옮기고 

A에 남은 하나는 쉽게 C로 옮길 수 있음 

B에 있는 n-1개를 A를 이용해서 C로 옮기면 끝 !

 

복잡도 O(n^2) 

더 효율적으로 구현할 순 없는듯..?!