백준 - 11729번(재귀)

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

11729번: 하노이 탑 이동 순서

import sys

n = int(sys.stdin.readline())

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

count = 2**n -1
print(count)
rec(n,1,2,3)

재귀를 이용한 하노이탑 문제다.

아이디어는 이렇다.

 

1. 원판이 1개라면? -> 1에서 3번으로 바로 이동

2. 원판이 2개라면? -> 가장 위의 원판을 2번에 옮겨놓으면 원판이 한개인 문제와 동일

3. 원판이 3개라면? -> 여기서 부터 조금 복잡하지만 2번을 생각해 보면 위에 두개를 2번에 옮겨놓기만 하면 1번 + 2번 문제가 된다.

그럼 2번으로 어떻게 옮기느냐? 1에서 3번으로 이동 1에서 2번으로 이동 3번에서 2번으로 이동 하면 된다.

 

n == 1일때 위의 순서에서 1번과 같은 상황이므로 종료 조건이다.

 

그럼 이제 최소 횟수를 생각해보자 n=1 -> 1회, n=2 -> 3회, n=3 -> 7회

 

n번째 원반을 한쪽 기둥으로 옮기는 데 필요한 최소 횟수를 an라고 하자. 

(n+1)번째 원반을 옮기려면(an+1을 구하려면) n번째 까지의 원반을 한쪽 기둥으로 옮기고(an​를 더하고) (n+1)번째 원반을 비어있는 기둥에 옮기고(1을 더하고) n번째까지의 원반을 (n+1)번째 원반 위로 옮기면(an​을 다시 더하면)된다.

 

a1​=1, an+1 ​ =2an​+1 을 만족하고 결론적으로 최소 횟수는 2**n -1 이 된다.

 

노베이스 상태에서 이런 아이디어를 바로 떠올리는건 어렵고 Well- Known 문제라서 난이도가 비교적 낮게 책정된 문제라고 생각한다.