1914번 하노이 탑

https://www.acmicpc.net/problem/1914

---

아이디어

백준 11729번 하노이 탑 이동 순서 문제와 거의 비슷했다.

하노이탑 원판 3개를 1번에서 3번으로 이동하기 위해서는
1. 원판 2개를 1번에서 2번으로 이동
2. 가장 큰 원판 1번에서 3번으로 이동
3. 나머지 원판 2개를 2번에서 3번으로 이동

일반화 시켜보자
하노이탑 원판 n개를 1번에서 3번으로 이동하기 위해서는
1. 원판 (n-1)개를 1번에서 2번으로 이동
2. 가장 큰 원판을 1번에서 3번으로 이동
3. 나머지 원판 (n-1)개를 2번에서 3번으로 이동

코드짤 때는 최종 목표는 원판 k개를 a에서 b 원판으로 이동한다고 생각했다. 그래서 다른 막대 하나는 c로 표시하는 게 아니라 (6-a-b)로 표시했다. 어차피 1+2+3 = 6이기 때문

# 원판 k개를 a -> b로 보낸다고 가정
hanoi(k-1, a, 6-a-b) # k-1개를 a -> c
print(a, b) # 가장 큰 원판 a -> b
hanoi(k-1, 6-a-b, b) # 다시 k-1개를 c -> b

---

코드

# 1 2 3
# a c b
def hanoi(k, a, b): # k개를 a->b
    if k == 1:
        print(a, b)
        return
    hanoi(k-1, a, 6-a-b) # k-1개를 a -> c
    print(a, b) # 가장 큰 원판 a -> b
    hanoi(k-1, 6-a-b, b) # 다시 k-1개를 c -> b

n = int(input())
print(2**n - 1)
if n <= 20:
    hanoi(n, 1, 3)

+) 출력 초과가 나왔는데 문제에서 N이 20 이하만 두 번째 줄부터 수행 과정을 출력하라고 되어있다.
즉, n이 21이상이면 재귀를 돌 필요가 없다.