[백준 1914번] 하노이 탑 - python / 재귀

문제 링크

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

1914번: 하노이 탑

 

풀이 

하노이탑의 이동 과정은 

1. a에 있는 n-1 개의 원반을 c를 거쳐 b로 옮긴다.

2. a에 남은 가장 아래 있는 원반을 c로 옮긴다. 

3. b로 옮겼던 n-1 개의 원반을 a를 거쳐 c로 옮긴다.

를 따르므로 위 과정을 재귀 함수로 반복해주면 된다. 

 

단, 여기서는 n이 20보다 큰 경우에 메모리 초과가 발생할 수 있으므로

20 이하일 때만 재귀함수를 실행하고 

20보다 클 때는 최소 이동 횟수인 2**n - 1 을 출력하면 된다. 

import sys
input = sys.stdin.readline

def hanoi(n, From, To, Sub):
    if n == 1 :
        answer.append((From,To))
        return 
        
    # From에 있는 n-1 개의 원반을 To를 거쳐 Sub로 옮기기
    hanoi(n-1, From, Sub, To)
    # From에 있는 하나의 원반을 To로 옮기기
    answer.append((From, To))
    # Sub로 옮긴 n-1개의 원반을 From을 거쳐 To로 옮기기 
    hanoi(n-1, Sub, To, From)
    
n = int(input())
answer = []

# n이 20 이하일 때만 실행 
if n <= 20:
    hanoi(n,1,3,2)
    print(len(answer))
    for i in answer:
        print(*i)
else:
    print(2**(n-1))