[BOJ/백준/C++] 11729번 하노이 탑 이동 순서

11729번: 하노이 탑 이동 순서

---

반응형

📌 접근 방법

✔️ 하노이 탑쌓기 문제

• n개의 원판을 첫번째 막대에서 세번째 막대로 옮기는 방법
  • n-1개의 원판을 첫번째에서 두번째로,
  • 마지막 원판을 첫번째에서 세번째로,
  • n-1개의 원판을 두번째에서 세번째로 옮기는 것이다.
• mid : 막대 1, 2, 3번 중 from에서 to로 가는 길에 들리는 막대이므로 6-from-to를 해줌

➡️ 재귀 함수 이용

 

 

✅  Pass Code

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<iterator>
#include<map>
#include<set>
#include<unordered_set>
#include <stack>
#include<queue>
#include<deque>

using namespace std;
void hanoi(int from, int to, int n){
    if(n==0)return;

    int mid=6-from-to;
    hanoi(from,mid, n-1);
    cout<<from<<' '<<to<<'\n';
    hanoi(mid,to,n-1);
}
int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;

    cin>>N;
    long long int a = pow(2,N)-1;
    cout<<a<<'\n';
    hanoi(1,3,N);

    return 0;
}