#11729번 하노이 탑 이동순서 (c++)

#include <iostream>
using namespace std;

int hanoi(int num){
    int total = 0;
    
    if(num==1){
        total++;
    }
    else{
        total+=hanoi(num-1);
        total++;
        total+=hanoi(num-1);
    }
    return total;
}

void print_hanoi(int num, int a, int b, int c){
    if(num==1){
        cout << a << " " << c << "\n";
    }
    else{
        print_hanoi(num-1,a,c,b);
        cout << a << " "<< c << "\n";
        print_hanoi(num-1,b,a,c);
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int num = 0;
    cin >> num;
    
    cout << hanoi(num) << "\n";
    print_hanoi(num,1,2,3);
    
    return 0;
}

기존의 하노이 탑 공식을 이용하면 쉽게 풀린다. 

다만, 총 이동 횟수를 먼저 적는 것을 단순 무식하게 함수 하나를 더 세워 풀었는데, 

다 풀고나서 다른 사람들의 풀이법을 구경해보니 '((1 << n)- 1)'로 풀린다는 사실을 발견했다. 

빨리 풀 생각에 더 나아가서 생각하지 못했기에, 더 보기좋고 깔끔한 공식은 생각 못했다.

더 차분하게 풀어보자.