백준 11729번 : 하노이의 탑 이동 순서 (Python)

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

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

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

n은 전체 원판의 수, start는 옮길 원판이 꽂혀있는 막대의 번호, end는 원판을 옮길 막대의 번호이다.

총 n개의 원판이 있을 때, 전체 과정은 크게 3단계로 구성된다.

1. n-1 개의 원판을 start도 end도 아닌 제 3의 막대(이 막대의 번호는 6 - start - end)로 이동

2. 가장 큰 원판을 start에서 end로 이동

3. 다시 n-1개의 원판을 end로 이동