PS/BOJ
[C++] 백준 11729번: 하노이 탑 이동 순서 - Recursion
__PS
2022. 7. 3. 16:27
728x90
https://www.acmicpc.net/problem/11729
11729번: 하노이 탑 이동 순서
세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로
www.acmicpc.net
하노이 탑에 사용하는 장대를 편의상 1, 2, 3번이라 부르면,
n-1개의 원반을 모두 1번에서 2번으로, 2번에서 3번으로 옮겨야 한다.
그러므로 n-1개의 원반을 1번에서 3번을 거쳐 2번으로, 그 다음에 2번에서 1번을 거쳐 3번으로 가는 경우를 생각하면 된다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
#include <iostream>
#include <cmath>
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(){
int n;
cin >> n;
cout << (int)pow(2, n)-1 << "\n";
hanoi(n,1,2,3);
}
|
cs |