[오일러 프로젝트 25] 피보나치 수열에서 처음으로 1000자리가 되는 항은 몇 번째?

피보나치 수열을 구할 때 보통 재귀호출과 동적계획법 등을 통해서 구하는 문제들이 많다. 그러나 이 문제는 1000자리 까지 구해야하기 때문에 unsigned long long 자료형으로도 표현할 수 없다! 이 문제도 마찬가지로 동적배열을 통해서 숫자를 표현해야한다.

 

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> fibo;
    fibo.push_back(1);

    vector<int> num;
    num.push_back(1);

    vector<int> tmp;

    unsigned int idx = 2;
    while (true) {

        tmp = fibo;

        for (int i = 0; i < num.size(); i++) {
            fibo[i] += num[i];
        }

        for (int i = 0; i < fibo.size(); i++) {
            if (fibo[i] >= 10) {
                int carry = fibo[i] / 10;
                fibo[i] %= 10;

                if (i == fibo.size() - 1) {
                    fibo.push_back(carry);
                }
                else {
                    fibo[i+1] += carry;
                }
            }
        }
        idx++;

        if (fibo.size() >= 1000) break;

        num = tmp;
    }

    cout << "index : " << idx << endl;
    for (int num : fibo) cout << num;
    
    cout << endl;
}

 

vector를 이용해서 실행시간이 느릴 것으로 예상했지만 생각보다 빠르게 결과를 얻어낼 수 있었다. ubuntu time 명령어로 측정해봐도 0.1초 이내에 답을 구해낼 수 있다.