[BOJ]1729-ハノイタワー移動順

質問リンク

最後のn個の基板は到達点(3)まで、1〜n−1の基板は2である.

作成する関数→n個の円板をa番柱からb番柱に移動する方法を出力する関数.

base condition → n == 1

回帰式→

n−1円板を柱aから柱6−a−bに移動させる.

n番の円板を柱aから柱bに移動します.

n−1円板をカラム6−a−bからカラムbに移動させる.

ex)K-1個の円盤を移動するにはA回の移動が必要で、K回目の円盤を到達地+1回、K-1個の円盤を到達地に移動するには、A回、合計2 A+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)