백준 #1914 하노이 탑

문제 링크

[1914 하노이 탑]

문제 설명

유명한 하노이탑 문제! 대신 $N$의 범위가 20이하일 경우 이동 과정 까지 출력해주어야함

코드

import sys
input = sys.stdin.readline


def hanoi(n, left, middle, right):
    if n == 1:
        print(left, right)
        return
    hanoi(n - 1, left, right, middle)
    print(left, right)
    hanoi(n - 1, middle, left, right)

N = int(input())
if N > 20:
    print(2**N - 1)
    exit()
print(2**N - 1)
hanoi(N, 1, 2, 3)

풀이

하노이 탑은 재귀 문제로 유명하다. $N-1$개의 원판을 보조 기둥(middle)에다가 옮기고 가장 큰 원판을 목표 기둥(right)에 옮긴 뒤에 다시 보조 기둥에 있던 $N-1$개의 원판을 left를 보조 기둥 삼아서 제일 오른쪽 목표기둥에 옮겨주면 끝!