1914: 하노이 탑

import sys

def hanoi(n, x, y):

    if n <= 20:
        if n > 1:
            hanoi(n-1, x, 6-x-y) #원판 갯수가 홀/짝일 때 다름
        print(x,y)
        if n > 1:
            hanoi(n-1,6-x-y,y)

n = int(sys.stdin.readline())

print(2**n-1)
hanoi(n, 1, 3)

재귀함수는 수학적 귀납법이라는 말이 있다.
'하노이 탑'은 대표적인 재귀함수 문제로 그 중에서도 매우 기본적인 문제다. 나 또한 최소 이동 횟수가 2**n-1임은 익히 알고 있었으나 n<=20일 때 중간과정을 출력하는 과정이 정말 어려웠다. 후에 해답을 보고 나니 허망할 정도로 간단했는데, 대부분의 재귀함수 문제들은 다들 이런 것 같다.

하노이 탑에서의 관건은 n번째 원판을 1번에서 3번으로 옮기는 것! 즉 n-1번 째 원판을 3번에서 2번으로 옮겨야 한다.
처음 코드를 분석했을 때는 '너무 결과론적이다.'라고 생각했다. 실제로 점화식을 찾을 때 결과값들을 써보면서 찾는 것이 정론이지만, 실제 문제를 풀 때 시간이 부족할 수 있으므로, 많은 경험을 쌓아두는 것이 필요하다.