하노이의 탑

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

def hanoi(n, frm, to, aux) -> int:
    if n == 1:
        print(f'{frm} {to}')
        return 1

    hanoi(n - 1, frm, aux, to)
    print(f'{frm} {to}')
    hanoi(n - 1, aux, to, frm)


K = int(input())
# K = 20
print(2 ** K - 1)
hanoi(K, 1, 3, 2)

재귀는 큰 문제를 분할해서 처리하는 특성 상 작은 문제를 해결하면 큰 문제도 해결된다. 수학적 귀납법처럼 k = 1, 2인 경우만 해결하면 자동으로 처리가 된다.

 

그를 위해서는 움직이는 방법을 재연할 수 있어야 한다. 일단 k = 1인 경우를 보자. 간단히 from -> to로 옮기면 된다

 

k = 2인 경우를 보자

k=1, 2에 대한 내용이 코드로 들어가있다. 이것은 다른 정수에도 적용이 된다.