[백준] 11729 - 하노이탑 - (python 파이썬)

문제링크 : https://www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

 

풀이과정 :

하노이탑은 엄청 어릴때,  수학경시대회나 어려운문제집 같은 곳 보면 풀었던 기억이 있는데,

다시보니까 또 어려웠다... 재귀함수에 대해서 어느정도 알고있다 생각했는데도 알고리즘을

정확히 이해하는데 시간이 걸렸다.  우선 1번 2번 3번 기둥을 각각 start(시작점) by(경유)

end(도착점)으로 정의하였으며 이는 각각의 상황에 따라 시작점이 경유점이 되기도,

경유점이 도착점이 되기도 한다.

 

결국 핵심은

경유점에 n-1개의 원판을 옮겨놓은 뒤, => hanoi(n-1, 시작, 도착, 경유)

하나 남은 원판을 시작점에서 도착점으로 옮기고 => print(start, end) #원판하나를 옮긴 행위

경유점에 있는 n-1개를 도착점에다가 다시 옮기는 것이다. => hanoi(n-1, by, start, end)

이 재귀과정에서 두번의 하노이 함수를 호출하기 때문에 2의 제곱씩 늘어나며, 

최종적인 원판을 옮기는 횟수는 (2**N-1)이 된다.

 

답

N = int(input())
def hanoi(n, start, by, end):
    if n == 1:
        print(start, end)
        return
    else:
        hanoi(n-1, start, end, by)
        print(start, end)
        hanoi(n-1, by, start, end)
print(2**N-1)
hanoi(N, 1, 2, 3)

답(이미지)

 

---

후기:

N의 범위가 20까지로 되어있는데 실제로 20을 대입해보니까.. 10초이상 걸리던데,

런타임에러가 안뜨는게 신기 ;ㅅ; ..