[단계별로 풀어보기][python 3] 재귀 - 하노이 탑 이동 순서 (11729)

11729번: 하노이 탑 이동 순서 (acmicpc.net)

11729번: 하노이 탑 이동 순서

방안 1

하노이의 탑을 실제로 시도해보면 다음과 같다.

이처럼 N개의 원판이 있으면 N-1개의 원판을 하노이의 방식대로 Auxiliary로 옮기고

Source의 원판을 Destination으로 옮긴 뒤 다시 N-1개의 원판을 Destination으로 옮긴다.

이 과정을 직접 해보면 원판의 개수 n에 따라 n**2-1번 움직이게 된다.

def hanoi(n, start, end):
    if n ==1:
        print(start, end)
        return
    
    hanoi(n-1, start, 6-start-end)
    print(start, end)
    hanoi(n-1, 6-start-end, end)

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