11729번 : 하노이 탑 이동 순서 - Python

문제

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

풀이

n개의 원반을 장대 1에서 장대3으로 옮기는 최소한의 횟수는 $2^n-1$이다.
재쉬는 n-1개의 원반을 1에서 2로 2에서 3으로 옮기는 방식으로 진행된다.

코드

import sys

input = sys.stdin.readline

def hannoi(n,f,w,to):
    if n==0:
        return
    else:
        hannoi(n-1,f,to,w)
        print('{} {}'.format(f,to))
        hannoi(n-1,w,f,to)

n = int(input())

print(2**n-1) # 최소이동 횟수
hannoi(n,1,2,3)

참고

https://mgyo.tistory.com/185