[BOJ] 11729 - 하노이 탑 이동 순서

문제 링크

마지막 n번째 원판이 도착지점(3)에 가려면 1부터 n-1까지의 원판은 2에 가있어야 한다.

• 만들어야 하는 함수 → 원판 n개를 a번 기둥에서 b번 기둥으로 옮기는 방법을 출력하는 함수

• base condition → n == 1

• 재귀 식 →

1. n-1개의 원판을 기둥 a에서 기둥 6 - a - b로 옮긴다.
2. n번 원판을 기둥 a에서 기둥 b로 옮긴다.
3. n-1개의 원판을 기둥 6 - a - b에서 기둥 b로 옮긴다.

ex) K-1개의 원판을 옮기는데 A번의 이동이 필요했다면 K번째의 원판을 도착지로 옮기는데 +1번, 또 다시 K-1개의 원판을 도착지로 옮기는데 A번 해서 총 2A + 1번이 필요

import sys
def hanoi(a, b, n):
    if n == 1:
        print('{} {}'.format(a, b))
        return
		# n-1개의 원판을 기둥 a에서 기둥 6 - a - b로 옮긴다.
    hanoi(a, (6 - a - b), n-1)
    # n번째 원판을 a에서 b로 옮긴다
    print('{} {}'.format(a, b))
		# n-1개의 원판을 기둥 6 - a - b에서  기둥 b로 옮긴다. 
    hanoi((6 - a - b), b, n-1)

k = int(sys.stdin.readline())
print((1<<k) - 1)
# 원판 1개를 옮기려면 1번, 2개를 옮기려면 3번, 3개를 옮기려면 7번이 최소횟수
# 이것을 구하는 과정에서 규칙을 구함.
hanoi(1, 3, k)