[백준] 11729번 하노이 탑 이동 순서

문제: 11729번: 하노이 탑 이동 순서

basic-algo-lecture/workbook/0x0B.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x0B.md at master · encrypted-def/basic-algo-lecture

 

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip> // setprecision을 사용하기 위한 헤더
#include <climits>
#include <list>

using namespace std;

void hanoi(int from, int mid, int to, int n) {
    if (n == 1) {
        // 옮겨야 할 원판이 1개인 경우
        cout << from << " " << to << "\n";
        return;
    }

    // n-1 개는 중간으로 옮기고 
    hanoi(from, to, mid, n - 1);

    cout << from << " " << to << "\n";

    // 맨 밑에를 to 로 옮기기
    hanoi(mid, from, to, n - 1);
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int k;
    cin >> k;
    

    cout << static_cast<int>(pow(2, k) - 1) << "\n";
    hanoi(1, 2, 3, k);


    return 0;
}

 

하노이탑 문제다. 강의에서 좋은 말을 해줬다. 재귀 문제는 절차적으로 생각하려고 하지 말고 귀납적으로 생각하라고 했다. 

 

이전에는 재귀 문제를 풀 때마다 재귀식이 돌아가는 단계를 직접 하나하나 다 확인해보려고 해서 이해가 되다가도 어느 순간 꼬여서 하기 싫었는데 이 행위를 버리고 최대한 귀납적으로 생각하려고 하니까 마음이 편해졌다.

 

하나하나 다 쫓아가면서 이해하려고 하지 말고 문제 풀의의 근본인 재귀식을 떠올리고 base condition 만 잘 설정해주는 게 재귀의 핵심임을 계속해서 기억해야 할 것 같다.

 

 

 

참고자료:

[바킹독의 실전 알고리즘] 0x0B강 - 재귀