[1914] 하노이 탑 / Big Integer 구현

문제 출처 : https://www.acmicpc.net/problem/1914

분류 : 재귀 호출

백준 1914 하노이 탑

BigInteger 를 C++에서 구현하기

---

구현 포인트

1) 재귀적으로 하노이탑을 구현

2) 100개의 원판까지 구현이 가능해야 하므로 숫자가 long long으로 표현되지 않는다.

3) 2)의 이유로 string으로 숫자를 구현해야 한다.

이 문제에서 얻어갈 수 있는 것은 2가지 정도이다.

1) JAVA에 있는 BigInteger를 C++ string으로 구현해 본다는 것이다.

unsigned long long범위(0~2^64-1)까지의 범위를 넘어가므로 따로 숫자를 저장하여 계산을 해주어야 한다.

2) float는 부동소수점 방식에 의해 2^100은 표현가능하지만 2^100-1은 표현할 수 없다.
(큰 수 일수록 표현가능한 숫자의 밀도는 적어지므로)

따라서 큰 수를 직접 다룰 수 있게 string으로 계산하여 최종적으로 답을 구해준다.

코드는 아래와 같다.

#include<cstdio>
#include<algorithm>
#include<string>
#include<cmath>
#include<vector>
using namespace std;
vector<pair<int, int> > seq;
void hanoi(int from, int to, int tmp, int n) {
    if (n != 1) {
        hanoi(from, tmp, to, n - 1);
        hanoi(from, to, tmp, 1);
        hanoi(tmp, to, from, n - 1);
    }
    else {
        seq.emplace_back(from, to);
    }
}
int main() {
    int n;
    scanf("%d", &n);
    if (n <= 20) {
        hanoi(1, 3, 2, n);
        printf("%lld\n", (long long)pow(2,n)-1);
        for (auto&p : seq) {
            printf("%d %d\n", p.first, p.second);
        }
    }
    else if(n<=63){
        printf("%lld\n", (long long)pow(2, n) - 1);
    }
    else {
        long long l = (long long)pow(2, 62);
        string str;
        for (int i = 0; i < 19; i++) {
            str.push_back(l % 10 + '0');
            l /= 10;
        }
        n -= 62;
        while (n--) {
            int carry = 0;
            for (int i = 0; i < (int)str.length(); i++) {
                int n = str[i] - '0';
                n = n*2+carry;
                str[i] = n % 10 + '0';
                carry = n / 10;
            }
            if (carry) {
                str.push_back(carry + '0');
            }
        }
        str[0]--;
        reverse(str.begin(), str.end());
        printf("%s\n",str.c_str());
    }
}