[Algorithm] 1일1솔 - 백준 11729 하노이의 탑 이동순서 (python3)

문제링크

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

11729번: 하노이 탑 이동 순서

 

문제설명

맨 아래 이외의 원반들은 목표장대가 아닌 보조장대로 옮기는 것을 재귀적으로 실행한다.

또한, n개의 원반을 이동시키기 위해서는 그 위의 n-1개의 원반을 다른 장대로 이동하고 맨 아래 원반을 도착지로 이동해야 한다. 그리고 다시 n-1개의 원반을 이동해야 하므로 다음과 같은 점화식이 성립한다.

a_n = 2a_(n-1) + 1

이를 일반항으로 풀어내면 총 이동횟수는 2^n - 1임을 알 수 있다. 

 

문제풀이

import sys

def hanoi(n, start, target, sub):	
    if n == 0:
        return
    hanoi(n-1, start, sub, target)  # 맨 아래 원반 이외의 원반들을 보조장대로 재귀적으로 옮기기
    print(start, target)			# 그 사이에 원반을 어디에서 어디로 한 번 옮길지 출력		
    hanoi(n-1, sub, target, start)  # 마지막으로, 보조장대로 옮겼던 원반들을 그 위에 얹는다.
    
n = int(sys.stdin.readline())
print(2**n - 1) # 이동 횟수 출력
hanoi(n, 1, 3, 2)