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

Interrobang 2022. 10. 9. 13:25

<문제 링크>

11729번: 하노이 탑 이동 순서

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로

www.acmicpc.net

<문제 풀이>

def hanoi(n, s, e): #hanoi(n개의 원판, 시작 장대, 도착 장대)
    if n == 1 : #원판이 1개인 경우
        print(s, e)
        return
       
    hanoi(n - 1, s, 6 - s - e)   #n-1개의 원판 중간 장대로 이동
    print(s, e)                  #가장 큰 원판 도착 장대로 이동
    hanoi(n - 1, 6 - s - e, e)   #n-1개의 원판 도착 장대로 이동
    
N = int(input())
print(2**N - 1) #옮긴 횟수
hanoi(N, 1, 3) #수행 과정

*key point: 하노이의 탑 최소 이동은 N-1개의 원판을 옮기고 가장 큰 원판을 옮긴 뒤 다시 N-1개의 원판을 그 위로 올린다는 간단한 원리로 구현가능하다. 점화식을 세워 일반항을 구해보면 옮긴 횟수는 2^N-1이 된다.

*reference: https://namu.wiki/w/%ED%95%98%EB%85%B8%EC%9D%B4%EC%9D%98%20%ED%83%91