반응형
https://www.acmicpc.net/problem/11729
💡 하노이 탑 이동 순서
✅ 문제 풀이
- 하노이 탑 문제는 재귀호출을 통해 풀이 할 수 있다.
- 하노이 탑의 다음과 같은 공식 때문이다.
- 탑 1에 있는 가장 작은 원판을 탑 3으로 옮긴다. 탑 3에 있는 가장 작은 원판을 탑 2로 옮긴다. 탑 2에 있는 가장 작은 원판을 탑 1로 옮긴다. 탑 1에 있는 가장 작은 원판을 탑 3으로 옮긴다.
- k-1개의 원판은 위 공식을 따르게 된다.
- 따라서 각 원판을 재귀 호출을 통해 이동 순서를 표현할 수 있다.
- 정리하자면, 1->3->2, 2->1->3 순서로 이동하게 된다.
- 이를 위해 hanoi라는 함수를 선언해준다.
- 이 함수는 현재 원판의 번호(=크기)와 시작(from), 중간(by), 끝(to) 지점을 인자로 갖는다.
만약 원판의 번호가 1이면 "from to"을 출력하도록 한다.
그렇지 않다면 hanoi를 호출하고 인자로 원판의 번호-1, from, to, by 순서로 넣어준다. 이는 1->3->2 순서를 나타낸 것이다.
그리고 이 함수를 호출한 후에는 "from to"를 호출하여 이동 상황을 출력한다.
그다음, hanoi를 한번 더 호출하여 인자로 원판의 번호-1, by, from, to 순서로 넣어준다. 이는 2->1->3 순서를 나타낸 것이다. - 따라서 원판 하나에 대해 hanoi 함수는 두번 재귀호출 하므로, 연산이 2^k번 발생하는데, 가장 큰 원판은 바로 이동할 수 있으므로 1을 빼준다. 따라서 총 이동 횟수는 2^k-1이 된다.
- 참고로 c++의 경우, pow함수를 사용할 때 int로 형변환을 해주지 않으면 결과가 틀렸습니다가 나오므로, int로 꼭 변환한 후 -1을 빼주도록 한다. (pow함수의 반환 형태는 double 형이기 때문)
✏ 코드 전문
#include<iostream>
#include<math.h>
using namespace std;
void hanoi(int n, int from, int by, int to) {
if (n == 1) {
cout << from << " " << to << "\n";
}
else {
hanoi(n - 1, from, to, by);
cout << from << " " << to << "\n";
hanoi(n - 1, by, from, to);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int k;
cin >> k;
cout << int(pow(2, k)) - 1 << "\n";
hanoi(k, 1, 2, 3);
return 0;
}
반응형
'CO-TE > 백준' 카테고리의 다른 글
[백준] 10026번 C++ "적록색약" 풀이 / dfs, 너비 우선 탐색 (0) | 2024.01.27 |
---|---|
[백준] 2447번 C++ "별 찍기 -10" 풀이 / 재귀, 분할정복, 프렉탈 (0) | 2024.01.24 |
[백준] 7576번 C++ "토마토" 풀이 / BFS, 너비우선탐색 (1) | 2024.01.22 |
[백준] 12865번 C++ "평범한 배낭" 풀이 / DP, 동적계획법 (0) | 2024.01.12 |
[백준] 1780번 C++ "종이의 개수" 풀이 / 분할과 정복, 재귀호출 (1) | 2024.01.12 |