[python] 백준 11729번 하노이 탑 이동 순서

백준 11729번 하노이 탑 이동 순서

https://www.acmicpc.net/problem/11729

문제

풀이

n = int(input())
answer = []
def hanoi (n, start, end, sub):
    if n == 1: 
        answer.append(str(start) + ' ' + str(end))
        return
    hanoi(n-1, start, sub, end)
    answer.append(str(start) + ' ' + str(end))
    hanoi(n-1, sub, end, start)

hanoi(n, 1, 3, 2)

print(len(answer))
for i in answer:
    print(i)

• n개의 원판이 있을 때, n-1개의 원판을 첫 번째 장대에서 두 번째 장대로 옮긴다.
• 가장 큰 원판을 세 번째 장대로 옮긴다.
• 두 번째 장대에 있는 n-1개의 원판을 세 번째 장대로 옮긴다.
  이 과정을 재귀적으로 진행한다.

📌 주의

하노이는 외우자.
이해가 안될 때 마다 https://www.youtube.com/watch?v=FYCGV6F1NuY&t=316s 영상을 보자.