[백준/11729] 하노이 탑 이동 순서 (with 파이썬)

✔ 문제

---

✔ 풀이

import sys
input = sys.stdin.readline

def hanoi(x, start, end):
    if x > 1:
        hanoi(x-1, start, 6 - start - end)

    print(start, end)

    if x > 1:
        hanoi(x-1, 6 - start - end, end)
        
n = int(input())
print(2**n - 1)
hanoi(n, 1, 3)

---

✔ 설명

하노이탑 규칙과 설명은 아래 유튜브를 참고하면 된다.

www.youtube.com/watch?v=FYCGV6F1NuY

 

 

6 - start - end 하는 이유가 뭔가 싶었는데 기둥의 번호를 1, 2, 3으로 준다면 기둥의 합이 1+2+3 = 6이라 6으로 주고 시작하는 것이다. 동영상에서 나오는 보조 기둥을 6-start-end로 사용해 따로 변수를 두지 않고 사용할 수 있다.

---

✔ 후기

증말 통곡의 하노이탑이다..

처음엔 6 - start - end가 뭔지 모르겠어서 계속 코드만 쳐다봤다.

코드는 짧은데 응축되어 있는 내용이 짧은 만큼 쉽지는 않아서 손으로 재귀 돌려가면서 다시 풀어봐야할 것 같다.

왜 알고리즘은 해도 안느는 것 같을까? ( ༎ຶŎ༎ຶ )