BOJ 11729 하노이 탑 이동 순서 c++

백준 11729 하노이 탑 이동 순서 문제.

 

* 1, 2, 3번 기둥이 있다고 하면 각각의 기둥은 6 - a - b 의 관계를 가짐.

 

#include <bits/stdc++.h>
using namespace std;

/*
    hanoi의 탑.
    1(a)번 기둥이 있고 2(b)번 기둥이 있으면 나머지 하나의 기둥은 (6-a-b)번 기둥임.
    n이 애초에 1인 경우를 생각해보면 a에서 b로 하나만 옮기면 됨.
    
    n이 1이 아닌 경우, n개의 기둥에서 n-1개 기둥을 6-a-b로 옮기면 됨.
    그리고 n 번째 원판을 a에서 b(목적지)로 옮김.
    
    그리고 다시 n-1 개 원판을 6-a-b에서 b번 기둥으로 옮기면 끝.
*/

int N;

void hanoi (int a, int b, int n) {
    if (n == 1) {
        cout << a << ' ' << b << '\n';
        return ;
    }
    hanoi (a, 6-a-b, n-1);
    cout << a << ' ' << b << '\n';
    hanoi (6-a-b, b, n-1);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N;
    cout << (1 << N) - 1 << '\n'; // 비트 연산자. 1을 n만큼 옮김. 이러면 2의 n승이 됨.
    hanoi(1, 3, N);
}