[백준 재귀] 하노이 탑 이동 순서 C++ (복습 필요)

시간 복잡도는 이해가 안갔다.

탑이 2개 일 때 옮기는 알고리즘이 재귀적으로 일어나야 하기 때문에 2인 경우를 예로 문제를 풀었다.

1->2

1->3

2->3

1	2
1	3
2	3

위 순서 대로 출력어야 하므로 입력 인자가 a b c 순서로 주어지면 a -> b , a -> c(출력), b ->c 순서로 알고리즘을 짯다.

#include <iostream>
#include <cmath>

using namespace std;

void hanoi(int start, int mid, int end, int n)
{
    if (n == 1)
    {
        cout << start << " " << end << "\n";
    }
    else
    {
        hanoi(start, end, mid, n - 1);
        cout << start << " " << end << "\n";
        hanoi(mid, start, end, n - 1);
    }
}
int main()
{
    ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    
    int n = 0;
    cin >> n;
    cout << (int)pow(2, n) - 1 << "\n";
    hanoi(1, 2, 3, n);
    return 0;
}