[오일러 프로젝트 16] 2^1000의 자리수 구하기

처음에 이 문제를 접근할 때 long double을 이용해서 해결을 하려고 했지만 숫자가 너무 컸기 때문에 자리수를 모두 구할 수 가 없었다. 자료형의 최대치를 넘어가는 숫자를 연산하려면 어떻게 해야할까? 단순히 동적배열에 연산을 하고 자리수에 해당하는 숫자를 연속적으로 할당하면 해결할 수 있다. 

 

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main() {

    vector<int> a;
    a.push_back(2);

    int cases = 999;
    while (cases--) {
        for (int idx = 0; idx < a.size(); idx++) a[idx] *= 2;
        for (int idx = 0; idx <= a.size() - 1; idx++) {
            if (a[idx] >= 10) {
                if (idx == a.size() - 1) {
                    int tmp = a[idx] / 10;
                    a.push_back(tmp);
                    a[idx] %= 10;
                }
                else {
                    int tmp = a[idx] / 10;
                    a[idx+1] += tmp;
                    a[idx] %= 10;
                }
            }
        }
    }

    int sum = 0;
    for (int num : a) {
        sum += num;
    }

    cout << sum << endl;

    return 0;
}

 

간단하게 해결할 수 있는 문제였는데 long double을 이용해서 해결하려다보니 시간이 너무 많이 소요됐다. 적절한 자료구조를 연상하는 연습이 더 필요한 것 같다.