[ 백준 / Python ] #1914 하노이의 탑

문제

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

1914번: 하노이 탑

Algorithm

재귀호출을 이용해서 풀었다.

 

이동횟수는 항상 2**n-1

1 1번 기둥에 N개 원판 있고,이를 3번 기둥으로 옮길때

2 1번 기둥에 위치한 N개의 원판 중 N-1 개를 2번으로 옮김

3 나머지 1개를 3번으로 옮김

4 2번 기둥에 있는 N-1개 원판을 3번 기둥으로 옮김

 

f(n,a,b,c): n개 원판 1번기둥 a, 2번기둥 b, 3번기둥 c

n=1이면 하나 옮기면 끝

n>1이면

1 1번의 N-1개를 2번으로 옮겨야 하므로 f(n-1,a,c,b)

2 나머지 1번의 1개를 3번으로 옮겨야 하므로 f(1,a,b,c)

2번 기둥에 잇는 n-1개를 3번으로 옮겨야 하므로 f(n-1,b,a,c)

Code

def f(n, a, b, c):
  if(n == 1):
    print(a, c, sep = " ")
  else:
    f(n-1, a, c, b)
    f(1, a, b, c)
    f(n-1, b, a, c)

n = int(input())
print(2**n-1)
if(n <= 20):
  f(n, 1, 2, 3)