[백준 11729번] [분할 정복/ 재귀] 하노이 탑 이동 순서

생각해보면 쉬운데, 분할정복이 아직 익숙하지 않아 쉽게 발견을 못했다.

 

항상 모든 문제를 풀 때, 큰 문제를 작은 문제로 나눠서 풀 생각부터 진행해야 한다.

즉, 이 문제를 분할 정복 문제로 느끼기 위해서는 근본적으로 제일 큰 덩어리와 나머지 묶음들을 움직이는 것으로 이해했어야 한다.

그러면 분할 정복 문제로 파악할 수 있다.

 

Divide and conquer하는 느낌을 잘 받아두도록 하자.

쪼개고 합해서 처리하고, 가장 작은 component는 직접 처리하는 양상을 이해해야 한다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
typedef pair<int, int> pii;
vector<pii> route;

void hanoi(int n, int from, int by, int to){
    // Base case
    if(n == 1) route.push_back(make_pair(from, to));
    else{
        hanoi(n - 1, from, to, by);
        route.push_back(make_pair(from, to));
        hanoi(n - 1, by, from, to);
    }
}

int main(void){
    fastio;
    int n;
    cin >> n;
    hanoi(n, 1, 2, 3);
    cout << route.size() << "\n";
    for(int i = 0; i < route.size(); i++){
        cout << route[i].first << " " << route[i].second << "\n";
    }
    return 0;
}