[Baekjoon] 1914번: 하노이 탑 (Gold) - C++ 풀이

임의 정밀도 / 큰 수 연산 재귀

💾 메모리: 2020 KB, 시간: 156 ms📅 2026년 2월 5일 17:06:14

문제 링크

문제 설명

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 5개인 경우의 예시이다.

입력

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 100)이 주어진다.

출력

첫째 줄에 옮긴 횟수 K를 출력한다.

N이 20 이하인 입력에 대해서는 두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다. N이 20보다 큰 경우에는 과정은 출력할 필요가 없다.

코드 (C++)

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int n;

void hanoi(int N, int from, int temp, int to)
{
    if (N == 1)
    {
        cout << from << " " << to << '\n';
        return;
    }
    hanoi(N - 1, from, to, temp); // 1 3 2
    cout << from << " " << to << '\n';
    hanoi(N - 1, temp, from, to); // 2 1 3
}

int main()
{
    cin >> n;

    string ans = "1"; // 1의 자리가 ans[0]에 오도록 유지

    for (int i = 0; i < n; i++)
    {
        int carry = 0;
        // 1의 자리부터 차례대로 2를 곱함
        for (char &c : ans)
        {
            int temp = (c - '0') * 2 + carry;
            c = (temp % 10) + '0'; // 현재 자리수 갱신
            carry = temp / 10;     // 올림수
        }
        // 마지막에 올림수가 남았다면 뒤에 붙임 (자릿수 확장)
        if (carry)
            ans += (carry + '0');
    }

    ans[0] -= 1;                     // 1의 자리는 항상 맨 앞에 있으므로 바로 뺄셈 가능
    reverse(ans.begin(), ans.end()); // 출력 직전에 딱 한 번만 뒤집기

     

    cout << ans << '\n';

    if (n <= 20)
    {
        hanoi(n, 1, 2, 3);
    }
}