문제 설명
•
세 개의 장대를 이용해 개의 원판을 최소 횟수로 첫 번째 장대에서 세 번째 장대로 옮기는 과정을 출력하는 문제
예제 입력/출력
•
입력1
3
Python
복사
•
출력1
7
1 3
1 2
3 2
1 3
2 1
2 3
1 3
Python
복사
제약 조건
•
문제 풀이
•
풀이1 재귀 -
◦
핵심 아이디어
1.
가장 큰 원판(N)을 제외한 나머지 N - 1개의 원판을 2번 기둥으로 옮긴다.
2.
가장 큰 원판을 3번 기둥으로 옮긴다.
3.
2번 기둥에 있는 N - 1개의 원판을 목표 기둥으로 옮긴다.
◦
점화식
▪
•
여기서 은 개의 원판을 옮기는 최소 이동 횟수
▪
◦
시간복잡도
▪
재귀 호출의 깊이가 이고, 매 단계마다 두 번의 재귀 호출이 발생하므로, 이동 횟수는
▪
따라서, 시간복잡도는
풀이 코드
def hanoi(a, b, n):
# Base Case: 원판이 1개일 때는 바로 목표 기둥으로 이동시킨다.
if n == 1:
print(a, b)
return
# 보조 기둥 번호
auxiliary = 6 - a - b
## 1단계: n-1개의 원판을 보조 기둥으로 이동시킨다.
hanoi(a, auxiliary, n - 1)
## 2단계: 가장 큰 원판을 목표 기둥으로 이동시킨다.
print(a, b)
## 3단계: 보조 기둥에 있는 n-1개의 원판을 목표 기둥으로 이동시킨다.
hanoi(auxiliary, b, n - 1)
n = int(input())
print(2**n-1)
hanoi(1, 3, n)
Python
복사
