[백준] 1914번 - 하노이 탑

아이디어

start -> final로 모든 원판을 이동한다면, 결국 모든 원판이 final로 이동되어야 하기 때문에 middle은 원판을 움직이기 위해 사용되는 보조기둥이다.
최종적으로는 final로 원판이 이동해야 한다.
원판이 총 n개라면 n-1개를 보조기둥으로 이동하고 가장 큰 원판을 final에 이동 후, 보조기둥에 뒀던 n-1개를 final로 이동하면 된다.
이때, 이 과정은 재귀적으로 동작하며, 보조기둥이 (start,middle,final) 중 어떤 기둥이 될지 지정해주면 된다.

코딩

N = int(input())

def hanoi(n,start,final,middle):
    if n == 1:
        print(start,final)
    else:
        hanoi(n-1,start,middle,final)
        print(start,final) # 제일 큰 원반 move
        hanoi(n-1,middle,final,start)

print(2**N-1)
if N <= 20:
    hanoi(N,1,3,2)