[Baekjoon] 1914번: 하노이 탑 (Gold) - C++ 풀이
문제
세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.
- 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
- 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.
이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.
아래 그림은 원판이 5개인 경우의 예시이다.
입력
첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 100)이 주어진다.
출력
첫째 줄에 옮긴 횟수 K를 출력한다.
N이 20 이하인 입력에 대해서는 두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다. N이 20보다 큰 경우에는 과정은 출력할 필요가 없다.
문제 조건
-
목표: 하노이 탑의 원판 N개를 옮기는 최소 이동 횟수를 계산하고, N이 20 이하인 경우에만 구체적인 이동 경로를 출력한다.
-
입력 상태: 원판의 개수 N은 1 이상 100 이하의 자연수이다.
-
핵심 조건: 이동 횟수 K는 2^N - 1로 계산되는데, N이 최대 100이므로 64비트 정수 범위를 초과하는 큰 수 연산(Big Integer)이 필요하며, 이동 경로는 N이 20 이하일 때만 출력하도록 제한해야 한다.
풀이
핵심 알고리즘
임의 정밀도 / 큰 수 연산
- 시간 복잡도: O(2^min(N, 20) + N^2) — 큰 수 계산에 O(N^2), 경로 출력에 최대 O(2^20) 약 1,048,576번의 연산이 수행된다.
핵심 아이디어
하노이 탑의 최소 이동 횟수인 2^N - 1을 계산하기 위해 문자열 기반의 큰 수 곱셈을 수행한다. N이 20 이하인 경우에만 재귀 알고리즘을 호출하여 이동 경로를 출력함으로써 시간 초과를 방지한다.
① 문자열을 이용한 2^N 계산
N이 최대 100인 경우 2^100은 약 1.26e30으로 long long 범위를 훨씬 초과한다. 따라서 숫자를 뒤집어서 저장(1의 자리가 인덱스 0)한 문자열에 2를 N번 곱하여 자릿수 올림(carry)을 직접 처리하는 방식으로 정확한 값을 구한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
string ans = "1"; // 1의 자리가 ans[0]에 오도록 유지
for (int i = 0; i < n; i++)
{
int carry = 0;
// 1의 자리부터 차례대로 2를 곱함
for (char &c : ans)
{
int temp = (c - '0') * 2 + carry;
c = (temp % 10) + '0'; // 현재 자리수 갱신
carry = temp / 10; // 올림수
}
// 마지막에 올림수가 남았다면 뒤에 붙임 (자릿수 확장)
if (carry)
ans += (carry + '0');
}
② 1 차감 및 결과 출력
하노이 탑의 공식은 2^N - 1이다. 2^N(N>=1)은 항상 짝수이므로 1의 자리인 ans[0]에서 1을 빼도 빌림(borrow)이 발생하지 않는다는 특이점을 이용하여 복잡한 뺄셈 로직 없이 계산을 마무리한 뒤, 뒤집힌 문자열을 원래 순서로 복구한다.
1
2
3
4
5
6
ans[0] -= 1; // 1의 자리는 항상 맨 앞에 있으므로 바로 뺄셈 가능
reverse(ans.begin(), ans.end()); // 출력 직전에 딱 한 번만 뒤집기
cout << ans << '\n';
③ 조건부 재귀 경로 탐색
N이 20보다 크면 출력해야 할 경로가 너무 많아(100만 줄 초과) 시간 초과가 발생하므로 문제의 조건에 따라 N이 20 이하일 때만 표준적인 하노이 재귀 함수를 호출하여 이동 순서를 출력한다.
1
2
3
4
if (n <= 20)
{
hanoi(n, 1, 2, 3);
}
④ 하노이 재귀 함수 구현
N-1개의 원판을 보조 기둥(temp)으로 옮기고, 가장 큰 원판을 목적지(to)로 옮긴 뒤, 다시 N-1개의 원판을 목적지로 옮기는 분할 정복 기법을 사용하여 최소 이동 경로를 생성한다.
1
2
3
4
5
6
7
8
9
10
11
void hanoi(int N, int from, int temp, int to)
{
if (N == 1)
{
cout << from << " " << to << '\n';
return;
}
hanoi(N - 1, from, to, temp); // 1 3 2
cout << from << " " << to << '\n';
hanoi(N - 1, temp, from, to); // 2 1 3
}
성능
-
메모리 : 2020 KB
-
시간 : 156 ms
코드 (C++)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int n;
void hanoi(int N, int from, int temp, int to)
{
if (N == 1)
{
cout << from << " " << to << '\n';
return;
}
hanoi(N - 1, from, to, temp); // 1 3 2
cout << from << " " << to << '\n';
hanoi(N - 1, temp, from, to); // 2 1 3
}
int main()
{
cin >> n;
string ans = "1"; // 1의 자리가 ans[0]에 오도록 유지
for (int i = 0; i < n; i++)
{
int carry = 0;
// 1의 자리부터 차례대로 2를 곱함
for (char &c : ans)
{
int temp = (c - '0') * 2 + carry;
c = (temp % 10) + '0'; // 현재 자리수 갱신
carry = temp / 10; // 올림수
}
// 마지막에 올림수가 남았다면 뒤에 붙임 (자릿수 확장)
if (carry)
ans += (carry + '0');
}
ans[0] -= 1; // 1의 자리는 항상 맨 앞에 있으므로 바로 뺄셈 가능
reverse(ans.begin(), ans.end()); // 출력 직전에 딱 한 번만 뒤집기
cout << ans << '\n';
if (n <= 20)
{
hanoi(n, 1, 2, 3);
}
}