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

<문제 링크>

11729번: 하노이 탑 이동 순서

 

<문제 풀이>

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) #수행 과정

11729입출력 예시

*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