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

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

11729번: 하노이 탑 이동 순서

📕 설명 📕

하노이 탑 알고리즘을 고려하여 문제 풀이.

 

재귀 중 가장 대표적인 문제.

 

1. 탈출 조건 설정하기

2. 일정 규칙 구현

3. 가장 큰 과정을 머릿속으로 구현하며 따라가기

 

이 과정에서 3가지 단계로 나눌 수 있다.

 

1번 : 하노이 탑 N - 1개를 가운데로 옮긴다.

2번 : 제일 큰 원판을 target 위치로 옮긴다.

3번 : N - 1개를 target 위치로 옮긴다.

 

 

 

🧑🏻‍💻 나의 풀이 🧑🏻‍💻

N = int(input())

move = []
print(2**N  - 1)
def hanoi(N, start, end):
    if N == 1:
        print(start, end)
        return
    hanoi(N - 1, start, 6-start-end)
    print(start, end)
    hanoi(N - 1, 6-start-end, end)
hanoi(N, 1,3)