[BOJ/python] 11729번 하노이 탑 이동 순서

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

11729번: 하노이 탑 이동 순서

 

문제 해석

장대는 3개이며, 원판의 개수 N을 입력받는다.

첫 번째 줄에 옮길 때의 최소 횟수 K를, 두 번째 줄 부터 수행과정을 출력한다.

---

코드

 

def move(n, a, b, c):
    if n == 0:
        return
    move(n-1, a, c, b)
    print(a, b)
    move(n-1, c, b, a)

n = int(input())

print(2**n - 1)
move(n, 1, 3, 2)

---

문제 풀이

재귀함수의 문제 유형 중 하나인 하노이의 탑 문제이다.

 

원판의 개수에 따른 최소 이동 횟수를 a_n 이라고 하자.
원판의 개수가 1인 경우 1번이면 되므로 a_1 = 1이다.

원판의 개수가 n인 경우:

n-1개를 2로 옮기고 n번째 원판을 3으로 옮긴 다음 n-1개를 3으로 옮기므로, a_n = 2a_(n-1) + 1,

(a_n + 1) = 2(a_(n-1) + 1) 이므로 b_n = a_n + 1 이라 하면 b_n = 2 b_2 이며, b_1 = 2 이므로
b_n = 2**n 이며, a_n = b_n - 1 이므로 a_n = 2**n - 1이 성립한다.