[C++] 백준 11729번: 하노이 탑 이동 순서 - Recursion

https://www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

 

하노이 탑에 사용하는 장대를 편의상 1, 2, 3번이라 부르면,

n-1개의 원반을 모두 1번에서 2번으로, 2번에서 3번으로 옮겨야 한다.

그러므로 n-1개의 원반을 1번에서 3번을 거쳐 2번으로, 그 다음에 2번에서 1번을 거쳐 3번으로 가는 경우를 생각하면 된다.

 

#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);
}