[BOJ/Step10] 11729 : 하노이 탑 이동 순서 (Python)

www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

---

n개의 원판을 1번 장대에서 3번 장대로 옮기려면

   1. n-1개의 원판을 1번 장대(출발)에서 2번 장대(중간)로 옮긴다 : 재귀

   2. 가장 큰 원판을 1번 장대(출발)에서 3번 장대(도착)로 옮긴다

   3. n-1개의 원판을 2번 장대(중간)에서 3번 장대(도착)로 옮긴다 : 재귀

3개의 과정을 거치고 총 2^n + 1번 이동이 필요하다. 

위 과정을 구현하면 hanoi(n, start, middle, goal) 이 된다.

# 11729.py

def hanoi(n, start, middle, goal):
    if n == 1:
        print(f'{start} {goal}')
    else:
        hanoi(n-1, start, goal, middle)
        print(f'{start} {goal}')
        hanoi(n-1, middle, start, goal)


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