백준 11729 하노이 탑 이동 순서/ C++

문제 : 링크텍스트

풀이 point

재귀를 이용한 문제 풀이, 원판이 몇 개 있든
1번 기둥에서 2번 기둥으로 n-1개를 올려놓고, 1번 기둥에서 3번으로 n번 원판을 올린 후 2번 기둥에서 3번 기둥으로 n-1개의 원판을 올려놓는다.

풀이 순서

1. n == 1일 떄 기저 조건 (n이 1일 경우는 1번에서 3번으로 옮기기만 하면 됨)
2. 1번 기둥에서 2번 기둥으로 n-1개의 원판을 옮김
3. 2번 기둥에서 3번 기둥으로 n개의 원판을 옮김

코드

//백준 1074, Z
#include <iostream>
#include <vector>
#include <queue>

void solve(int a, int b, int n){
    if(n==1){
        std::cout << a << ' ' << b << '\n';
        return;
    }
    solve(a, 6-a-b, n-1); //1번 기둥에서 2번 기둥으로 n-1개 옮김
    std::cout << a << ' ' << b << '\n';
    solve(6-a-b, b, n-1); //2번 기둥에서 3번 기둥으로 n개 옮김

    
}

int main(){

    int N;
    std::cin >> N;
    std::cout << (1<<N) - 1 << '\n';
    solve(1, 3, N);

    return 0;
}