[백준 11729] 하노이 탑 이동 순서 (C++)

하노이탑은 진짜 웰논이다... 위의 그림처럼 원판 5개가 놓여있으면 위에 있는 4개 원판을 2번 기둥에 옮겨야한다. 이는 원판 4개인 경우의 하노이탑과 굉장히 유사하다. N개의 원판을 현재 기둥에서 다른 기둥으로 옮길 때, 하노이탑 규칙을 준수하며 옮기기 때문이다.

따라서, 원판이 N개인 경우를 해결하려면, N-1인 경우를 또 해결해야하는 상황인 것이고 이를 재귀를 통해 쉽게 해결이 가능할 것이다.

이를 코드로 옮기면 다음과 같다.

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

int n, cnt = 1;

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;
    for (int i = 0; i < n; i++) cnt *= 2;
    cout << cnt - 1 << "\n";
    hanoi(n, 1, 2, 3);
}