백준 알고리즘 1914: 하노이 탑

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

1914번: 하노이 탑

문제 

문제 해결을 위한 과정

이 문제는 재귀 함수와 관련이 된 문제였습니다. 하노이 탑에서 각각의 원판을 이동시킬 때 제약조건에 맞추어서 이동을 시켜야 합니다. 하노이 탑에서 원판을 이동하는 과정을 재귀로 표현하는 것의 핵심은 원판의 이동하는 과정을 점차 점차 작게 줄여나가는 데 있습니다. 먼저 원판이 3개 A, B, C 방식으로 이루어져 있다면 이는 다음과 같습니다.

 

A를 1번에서 3번으로

B를 1번에서 2번으로

A를 3번에서 2번으로

C를 1번에서 3번으로

A를 2번에서 1번으로

B를 2번에서 3번으로

 A를 1번에서 3번으로 

 

이는 다시 말하면 A,B를 2번 기둥으로 옮긴 후 C를 3번 기둥으로 옮기고 다시 A, B를 3번 기둥으로 옮기는 것입니다. 

A, B, C, D의 경우도 마찬가지로 A, B, C를 옮기는 경우에 D를 더 옮기는 경우라고 볼 수 있습니다.

A, B, C, D, E의 경우도 마찬가지로 A, B, C, D를 옮기는 경우에 E를 더 옮기는 경우라고 볼 수 있습니다. 

이를 일반화 하면 N개를 옮기는 경우 N-1을 옮기는 경우와 1개를 옮기는 과정으로 바꿀 수 있다는 것입니다.

 

문제 해결을 위한 팁

문제를 살펴보면 N이 20 이하인 경우 출력 예시처럼 출력을 하고 그 외의 경우 즉 20을 초과하는 경우는 단순히 몇 번을 옮겨야 하는지만 출력하라고 하였습니다. 이는 숫자가 너무 커져 메모리 초과를 막기 위한 조건입니다.  따라서 이는 재귀를 통해 횟수를 구하는 것이 아닌 일종의 점화식을 구하라는 것을 문제에서 암묵적으로 힌트를 주는 것임을 알 수 있습니다.  그렇다면 규칙을 파악해봅시다.

N이 1일 때 횟수 1

N이 2일 때 횟수 3

N이 3일 때 횟수 7

 N이 4일 때 횟수 15

 N이 5일 때 횟수 31

 

 

결국 점화식은 다음과 같습니다.

 소스코드

 

N = int(input())
ans = []
 
def HaniTower(num, fromi, by, to):
  if num == 1:
    ans.append((fromi, to))
  else:
    HaniTower(num-1, fromi, to, by)
    ans.append((fromi, to))
    HaniTower(num-1, by, fromi, to)    
 
if N <= 20:
  HaniTower(N, 1, 2, 3)
elif N > 20:
  answer = 2 ** N - 1
  print(answer)
 
if N <= 20:
  length = len(ans)
  print(length)
  for i in range(length):
    print(ans[i][0], ans[i][1])