[알고리즘/백준]11729 : 하노이 탑 이동 순서(python)

n개의 원반 옮기는 경우를 an이라고 하면
an+1의 경우 가장 큰 n+1원반을 옮기기 위해 n개를 옮겨야한다.
n개의 원반을 1 -> 2로 옮기는게 an
n+1원반을 3으로 옮기는게 1
다시 n개 원반을 2 -> 3 an
-> an+1 = 2an + 1...
2^n - 1

1. 가장 큰 원판 n은 맨 밑에 있어야한다. n-1개를 두번째로 옮김
2. n을 3으로 옮김
3. n-1개를 두번째에서 세번째로 옮김

def hanoi(n, start, to, end):
    if n == 1:
        print(start, end)
    else:
        hanoi(n - 1, start, end, to)
        print(start, end)
        hanoi(n - 1, to, start, end)


n = int(input())
print(2**n - 1)
hanoi(n, 1, 2, 3)