1914

날짜 : 2023. 03. 29

사용 언어 : python

 

문제

 

 

코드

import sys


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


def hanoi(x, y, z, cnt):  # start, via, end, 최대 원판의 수
    if cnt == 0:
        return
    hanoi(x, z, y, cnt - 1)  # start -> via 이동, end 활용 // cnt 위의 원판들 이동
    print(x, z)  # 맨 밑의 원판 이동(cnt)
    hanoi(y, x, z, cnt - 1)  # via -> end 이동, start 활용 // cnt 위의 원판들 이동

print(2**n - 1)
if n <= 20:
    hanoi(1, 2, 3, n)  # 1에서 3으로 이동, 2를 활용 // n개의 원판

 

 

풀이

- 재귀를 이용해 하노이의 탑을 구현한다.

 

 

 

알게된 점

- 원판은 오름차순으로 정렬되어 있다고 가정한다.

- n번째 원판을 옮기기 위해서는 (n-1)번째 원판까지 전부 이동시켜야 한다.

- 즉, 원판 n을 x에서 z로 옮기기 위해서는 1부터 n-1번째 원판을 전부 x에서 y까지 옮긴 후,

  n번째 원판을 x에서 z로 옮긴 다음, 

  1~(n-1)번째 원판을 y에서 z로 옮겨야 한다.

- 그러므로 옮길 원판의 위의 원판들을 전부 다른 곳으로 빼 놓은 다음 해당 원판을 옮긴 후 (print 함수를 통해 출력) 나머지 원판들을 경유지에서 도착지로 옮기는 것을 재귀적으로 구현한다.

 

- 오랜만에 풀어보는 문제라 조금 고민했지만 풀어보니까 그래도 이해는 되었다.

 

 

 

참고 사이트

-