[BOJ][Python][실2][11729] 하노이 탑 이동 순서

문제 링크

문제링크

첫 번째 풀이

정답코드

n개를 옮기기 위해선 1-n개를 다 옮긴 뒤, 제일 큰하나를 옮기면 된다. 이 과정을 재귀적으로 진행한다.

import sys
from math import pi, sqrt
from collections import deque

arr = []


def hanoi(n, curr, temp, target):
    if n == 1:
        arr.append((curr, target))
        return
    # 1 ~ n-1 : curr -> temp
    hanoi(n - 1, curr, target, temp)
    # n : curr -> target
    arr.append((curr, target))
    # 1 ~ n-1 : temp -> target
    hanoi(n - 1, temp, curr, target)


# 파일 입력
# sys.stdin = open('input.txt', 'r')
n = int(sys.stdin.readline())

hanoi(n, 1, 2, 3)
print(len(arr))
for i in arr:
    print(*i, sep=' ')

Success Notice: 수고하셨습니다.