[백준][C++] 2749번: 피보나치 수 3 <194>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

 

생각의 흐름

우선 이 문제는 피사노 주기 에 대한 개념이 있어야 풀 수 있다.

다음 문제를 먼저 풀어보기를 권장한다.

[백준][C++] 9471번: 피사노 주기 <193>

다른 블로그의 풀이를 보면 이미 주기를 안다는 가정하에 푸는 분들이 있는데....

(아니 솔직하게 그 주기를 누가 외우고 다닙니까....)

 

따라서 주기를 모르는 상태에서 수열과 주기를 둘 다 구할 수 있는 함수를 만들어서 풀이를 하였습니다.

 

pisano함수에서는 초기의 피보나치 수열 0,1,1을 벡터 vec에 push 하고 주기를 구할 때까지 무한루프를 돌게 됩니다.

그리고 주기(i)를 구하면 루프를 종료하면서 주기 i 를 반환하게 됩니다.

 

나머지 들의 반복 주기를 알게 되었으니, 이제 주어진 수 N을 MOD로 나눈 나머지 index에 해당하는 vector의 값이 답이 됩니다.

 

나의 코드

#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000

long long n;
vector<int> vec;

long long fisano(){
    vec.push_back(0);
    vec.push_back(1);
    vec.push_back(1);

    long long i = 2;
    while(true){
        vec.push_back((vec[i] + vec[i - 1]) % MOD);
        i++;
        if(vec[i] == 0 && vec[i-1] == 1) break;
    }
    return i;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;

    long long len = fisano();
    cout << vec[n % len];

    return 0;
}