[백준] 2749번 : 피보나치 수 3

Kim Yuhyeon·2022년 7월 5일

백준 알고리즘

알고리즘 + 자료구조

목록 보기

68/161

https://www.acmicpc.net/problem/2749

문제

알고리즘 접근 방법

피사노 주기(Pisano Period)

행렬 이용

풀이

피사노 주기(Pisano Period)

#include <iostream>
using namespace std;
const int mod = 1000000;
const int p = mod/10*15;


int fibo[p] = {0,1};
int main() {
    long long n;
    cin >> n;
    for (int i=2; i<p; i++) {
        fibo[i] = fibo[i-1] + fibo[i-2];
        fibo[i] %= mod;
    }
    cout << fibo[n%p] << '\n';
    return 0;
}