[C언어] 백준 2749 : 피보나치 수 3

백준 2749 : 피보나치 수 3

 

문제 링크

www.acmicpc.net/problem/2749

2749번: 피보나치 수 3

 

 

문제 내용

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그다음 2번째부터는 바로 앞 두 피보나치 수의 합이 된다.

 

n이 주어질때, n번째 피보나치 수를 1,000,000으로 나눈 나머지를 출력한다.

 

 

Idea

이 문제를 시간초과 없이 풀기 위해서는 피사노 주기를 알아야한다.

피사노 주기란 피보나치 수를 m으로 나눈 나머지가 주기를 이룬다는 것이다. 즉, 일정한 패턴이 존재한다는 뜻이다.

• 피사노 주기에 대한 문제 링크(백준 9471번)

위 문제를 풀어봤다면 간단하다. 만든 코드에 1,000,000을 넣으면 주기로 1,500,000이 나오는데 이는 150만 번마다 주기가 반복된다는 의미이다.

 

 

Code

#include <stdio.h>
 
int fibo[1500000];
 
int main() {
    long long int n;
    scanf("%lld", &n);
 
    fibo[0] = 0;
    fibo[1] = 1;
 
    for (int i = 2; i < 1500000; i++)
        fibo[i] = (fibo[i - 1] + fibo[i - 2]) % 1000000;
 
    printf("%d\n", fibo[n % 1500000]);
    return 0;
}