문제

설명

큰 문제를 작은 문제로 쪼개는 아이디어.
분할정복으로써 당연한 아이디어고 절차였다.
쪼개는 프로세스를 생각하는 게 중요해 보인다.

한 문제는 세 과정으로 쪼개진다.
1. 제일 큰 판을 제외한 나머지를 via로 이동
2. 제일 큰 판을 to로 이동 (출력 비용 발생)
3. 나머지를 to로 이동

이외에는 하노이의 탑을 해결하는데 걸리는 이동횟수가 2^n - 1 이라는 점을 알 필요가 있다.
n의 최대크기 100에 의해 정수 표현 범위를 벗어나므로 나는 string을 이용해 문제를 해결했다.
2^n 은 항상 마지막 자리 수가 2 이상이므로, 끝자리에 -1을 하더라도 정확한 결과가 나올것이라고 생각했다.

코드

// 2022.02.28 11:23:38
// 1914_2 https://boj.kr/1914_2
#include <bits/stdc++.h>
using namespace std;

void hanoi(int left, int from, int via, int to)
{
    // 한 문제는 3과정으로 쪼개진다.
    // 1. 제일 큰 판을 제외한 나머지를 via로 이동
    // 2. 제일 큰 판을 to로 이동
    // 3. 나머지를 to로 이동

    if (left == 1)
    {
        cout << from << ' ' << to << '\n';
        return;
    }

    hanoi(left - 1, from, to, via);
    cout << from << ' ' << to << '\n';
    hanoi(left - 1, via, from, to);
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    string ans = to_string(pow(2, n));
    ans = ans.substr(0, ans.find('.'));
    --ans[ans.length() - 1];
    cout << ans << '\n';
    if (n <= 20)
        hanoi(n, 1, 2, 3);
}