[BOJ] 2749 - 피보나치 수 3 (C++)

문제

피보나치 수 3

코드

#include <iostream>
#include <vector>

using namespace std;

long long N, cnt, mod = 1000000;
vector<int> v;

void solve(){
    cnt = 2;

    while (1){
        v.push_back((v[cnt]+v[cnt-1])%mod);
        cnt++;
        if (v[cnt] == 0 and v[cnt-1] == 1) break;
    }
}

int main(void){
    cin >> N;
    v.push_back(0); v.push_back(1); v.push_back(1);
    solve();
    cout << v[N%cnt];
    return 0;
}

접근

문제 해결을 위해 피사노 주기를 이용하였다. 간단하게 말하자면 피보나치 수열을 m으로 나눈 나머지가 주기를 이룬다는 것이다. 즉 나머지의 주기를 알 수 있다면 실제 값을 구하여 나누어 값을 계산하지 않고도 원하는 결과를 구할 수 있는 것이다. 따라서 피사노 주기를 구하기 위해 무한루프를 맨 마지막 값이 0, 그 전 값이 1일 때까지 반복하였다. 이후 값은 다시 1이 되어 한 바퀴를 돈 것이라 확인할 수 있기 때문이다. 주기를 구한 후에는 입력 값을 주기로 나누어 결과를 얻을 수 있었다.

참고
https://cocoon1787.tistory.com/307