[C++]프로젝트 오일러 25번 문제&풀이 (피보나치 수열에서 처음으로 1000자리가 되는 항은 몇 번째?)

문제 25번

피보나치 수열은 아래와 같은 점화식으로 정의됩니다.

Fn = Fn-1 + Fn-2  (단, F1 = 1, F2 = 1).

이에 따라 수열을 12번째 항까지 차례대로 계산하면 다음과 같습니다.

F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144

수열의 값은 F12에서 처음으로 3자리가 됩니다.

피보나치 수열에서 값이 처음으로 1000자리가 되는 것은 몇번째 항입니까?

 

접근방법

1. 우선 numVec_1 벡터와 numVec_2 벡터에 1을 담고 이 두 벡터의 합이 numVec_3 벡터가 되도록 세팅한다.

2. 1000자리수까지 계산해야 하므로, numVec_3 벡터에 3자리씩 끊어서 넣어주면 999자리수까지는 333칸이고, 1000자리 넘어가는 순간 numVec_3 벡터의 334번째 칸이 바뀌는데, 이때의 count 값이 이 문제의 정답이다.

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
    vector<int> numVec_1(334), numVec_2(334), numVec_3(334);

    int count = 3;

    numVec_1[0] = 1;
    numVec_2[0] = 1;

    while (numVec_3[333] == 0)
    {
        numVec_3.assign(334, 0);
        
        for (int n = 0; n < 334; n++)
        {
            numVec_3[n] = numVec_1[n] + numVec_2[n];
        }

        for (int n = 0; n < 333; n++)
        {
            if (numVec_3[n] >= 1000)
            {
                numVec_3[n] -= 1000;
                numVec_3[n + 1]++;
            }
        }

        for (int n = 0; n < 334; n++)
        {
            numVec_1[n] = numVec_2[n];
            numVec_2[n] = numVec_3[n];
        }

        count++;
    }

    cout << endl;

    for (int n = 0; n < numVec_3.size(); n++)
    {
        cout << numVec_3[n] << " ";
    }
    cout << endl;
    cout << endl;

    cout << "Answer is : " << count-1 << endl;

    return 0;
}

참고

https://github.com/mannlim/ProjectEuler

mannlim/ProjectEuler