백준 11729 파이썬 (하노이 탑 이동 순서)

문제 : https://www.acmicpc.net/problem/11729
알고리즘 분류 : Recursion

💻 Code

n = int(input())

def hanoi(n, start, mid, dest):
    if n == 1:
        print(start, dest)
    else:
        hanoi(n-1,start, dest, mid)
        print(start, dest)
        hanoi(n-1, mid, start, dest)

print(2**n-1) # 2의n승 - 1 (하노이탑 이동횟수)
hanoi(n,1,2,3)

1. n개의 원판이 있을 때, n-1개의 원판 즉, 맨 밑의 원판을 제외하고 나머지 원판들을 1번에서 2번으로 옮긴다.
   hanoi(n - 1, a, c, b)
2. 맨 밑의 원판을 1번에서 3번으로 옮긴다.
   if n == 1: print(a, c)
3. 그리고 n-1개의 원판들을 다시 2번에서 3번으로 옮긴다.
   hanoi(n - 1, b, a, c)