🔗 수학적 귀납법을 통한 재귀를 사용하면 풀 수 있는 문제이다.

n = 1인 경우

시작점에 원판이 하나 있다면 바로 목적지로 옮기면 된다. 즉 한 번의 이동으로 옮길 수 있다.

n = k일때 옮길 수 있다고 가정하고, n = k+1일 경우

원판이 k일때 도착지로 모두 옮길 수 있다고 가정했다. 한편, 하노이 탑의 규칙상 큰 원판이 작은 원판 위에 오지 못한다. 따라서 이 규칙에 맞게 k개의 원판을 임시 위치에 옮긴 다음, 제일 큰 원판을 도착지로 옮기고, 나머지 원판을 임시 위치에서 도착지로 옮기면 문제를 해결할 수 있다.

이동 횟수에 대한 일반항

W(1) = 1 $\\$ W(2) = 2W(1) + 1 = 3 $\\$ W(3) = 2W(2) + 1 = 7 $\\$ W(4) = 2W(3) + 1 = 15 $\\$ W(5) = 2W(4) + 1 = 31 $\\$ ... $\\$ W(n) = 2W(n-1) + 1 $\\$ $W(n) = 2^n - 1$

위 일반항을 수학적 귀납법으로 증명해 보자

• Base Case (n = 1) $W(1) = 1 = 2^1 - 1$
• $k \ge 1$인 $k$에 대해 성립한다고 가정할 때 $n=k+1$은 $\\$ $W(k+1) = 2W(k) + 1 \\ = 2(2^k - 1) + 1 \\ = 2^{k+1} - 2 + 1 \\ = 2^{k+1} - 1$ 으로 식이 성립힌다.

$\therefore W(n) = 2^{n} - 1$

DP 사용

위 방식만으로도 이 테스트케이스 범위 내에서 문제를 충분히 해결할 수 있다. 하지만 코드를 더 최적화하기 위해 메모이제이션 기법을 사용했다. 파이썬 dict 자료구조를 통해 f"{n},{start},{end},{via}"를 키로 사용하여 계산 결과를 저장하고, 중복 계산을 방지하므로써 코드를 최적화할 수 있었다.

코드

import sys

dp = {}

def hanoi(n, start, end, via):
    if (n == 1):
        return f"{start} {end}\n"
    
    if (f"{n},{start},{end},{via}" in dp):
        return dp[f"{n},{start},{end},{via}"]
    
    res = ""
    res += hanoi(n-1, start, via, end)
    res += f"{start} {end}\n"
    res += hanoi(n-1, via, end, start)
    dp[f"{n},{start},{end},{via}"] = res
    return res


n = int(sys.stdin.readline())
sys.stdout.write(f"{(2**n)-1}\n")

if (n <= 20):
    sys.stdout.write(hanoi(n, 1, 3, 2))