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

문제

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

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 n번째 피보나치 수를 1,000,000으로 나눈 나머지를 출력한다.

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

풀이

입력값이 100경? 이정도연산은 O(N)으로 풀수없다. 알고리즘 힌트를 보니 분할정복을 이용하여... 풀수있다는데,
그전에 피보나치 주기란것이 있어서 참고했다.
피보나치 주기란 피보나치수를 M=10^k 로 나눌때 항상 15x10^(K-1)이 주기가됨을 의미한다. (K>2)
100으로 나눈다면 그 주기가 150이 된다는소리이다. 따라서 문제에서 1000000으로 나눈나머지를 출력하므로,
모든연산에 MOD = 1000000을 정의하여 나누고, 이때 피보나치주기는 1500000 가된다.

여기서 중요한것이.
이부분에서 MOD로 한번더 안나눠주면 값이 더 커질수있어 오류가난다.
무조건 내부적인 모든 요소에 MOD로 나누고, 마지막에 한번더 MOD로 나누어주어야한다.

아래는 전체 코드

#define _CRT_SECURE_NO_WARNINGS 
#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
const int MOD = 1000000;

//피사노 주기 : M=10^k 로 나눌때 주기는 항상 15x10^(k-1)임.
//여기서 k = 6이므로 15x10^5 수가 반복된다

int main(void) {
	long long N, ppre = 1, pre = 0, current = 0;
	scanf("%lld", &N);
	N %= 1500000;
	while (N--) {
		current = (ppre % MOD + pre % MOD)% MOD;
		ppre = pre % MOD;
		pre = current;
	}
	printf("%lld", current);

	return 0;
}