https://www.acmicpc.net/problem/1914
1914번: 하노이 탑
세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로
www.acmicpc.net
문제
문제 해결을 위한 과정
이 문제는 재귀 함수와 관련이 된 문제였습니다. 하노이 탑에서 각각의 원판을 이동시킬 때 제약조건에 맞추어서 이동을 시켜야 합니다. 하노이 탑에서 원판을 이동하는 과정을 재귀로 표현하는 것의 핵심은 원판의 이동하는 과정을 점차 점차 작게 줄여나가는 데 있습니다. 먼저 원판이 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
결국 점화식은 다음과 같습니다.
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
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])
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 18352: 특정 거리의 도시 찾기(Python) (0) | 2020.12.04 |
|---|---|
| 백준 알고리즘 15686: 치킨 배달 (Python) (0) | 2020.11.30 |
| 백준 알고리즘 3190: 뱀(Python, c++) (0) | 2020.11.29 |
| 백준 알고리즘 18406: 럭키 스트레이트 (Python) (0) | 2020.11.27 |
| 백준 알고리즘 1439: 뒤집기 (Python) (0) | 2020.11.25 |