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

백준 - 2749

 

---

풀이

Pisano Period를 이용해 풀이했다.

Wikioedia - Pisano period

위의 내용 처럼 피보나치 수를 특정 수(n)으로 나눌 때 나머지들은 일정 주기마다 반복되는 것을 알 수 있다.

이러한 주기를 Pisano Period라고 부른다. 

 

Pisano Period는 다음과 같이 이용된다.

• n번째 피보나치 수를 MOD로 나눈 나머지는, N % (Pisano Period) 번째 피보나치 수를 MOD로 나눈 나머지와 같다.

Pisano Period번 째의 피보나치 수가 필요하며, 이번 문제에 필요한 Pisano Period를 구하는 방법은 다음과 같다.

• MOD가 10의 6승이므로 Pisano Period는 1500000 = 15 * 10 ^(5) 이다.

 

---

소스코드

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

---

출처 및 참고자료

2749번: 피보나치 수 3

Pisano period - Wikipedia

[백준 9471] 피사노 주기 [C]