백준1914 하노이 탑

작성일 | In

문제 링크

  • http://icpc.me/1914

시간복잡도

  • N <= 20이라면 O(2N)
  • N > 20이라면 O(log N)

풀이

약 2^100을 구하는 코드를 C++로 작성하기 싫어서 python으로 풀었습니다.
먼저, 원판이 N개 있다면 이동 횟수는 항상 2N-1입니다.

1번 기둥에 N개의 원판이 있고, 3번 기둥으로 옮겨야 한다고 합시다.
N개의 원판을 모두 3번 기둥으로 옮기는 방법은 아래와 같습니다.

  1. 1번 기둥에 위치한 N개의 원판 중, 위에 있는 N-1개의 원판을 2번 기둥으로 옮긴다.
  2. 1번 기둥에 남아있는 1개의 원판을 3번 기둥으로 옮긴다.
  3. 2번 기둥에 있는 N-1개의 원판을 3번 기둥으로 옮긴다.

이를 재귀함수로 구현해봅시다.
f(n, a, b, c) : n개의 원판이 a기둥에 있을 때, c기둥으로 모두 이동시키는 함수 로 정의합시다.
만약 n = 1이면 a에서 c로 하나 옮기고 끝내면 되겠죠.
나머지 경우를 살펴봅시다.

  1. a번 기둥에 위치한 N개의 원판 중, N-1개를 b번 기둥으로 잠시 옮겨야 하니 f(n-1, a, c, b)를 호출합니다.
  2. a번 기둥에 남아있는 1개의 원판을 c로 옮겨야 하니까 f(1, a, b, c)를 호출합니다.
  3. b번 기둥에 잠시 놓았던 N-1개를 c번으로 옮겨야 하니까 f(n-1, b, a, c)를 호출합니다.

이렇게 3단계만 작성하면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
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)