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

앞의 글을 참조해야 한다

피사노 주기를 통해서 어떤 피보나치 수를 1000000으로 나눈 주기는 1500000이다.

따라서 n에 어떤 수가 들어오더라도

n mod 1500000의 값만 찾으면 된다.

또한 미리 피보나치 배열을 하나 만들어 놓으면 메모리 누수가 적을 것이다.

 

#include <iostream>
#include <vector>
using namespace std;

long long a[1500010];

void fibo() {
	a[0] = 0;
	a[1] = 1;
	for (int i = 0; i < 1500000; i++) {
		a[i + 2] = (a[i + 1] + a[i]) % 1000000;
	}
}

int main() {

	long long n;
	cin >> n;
	fibo();
	cout << a[n % 1500000] << "\n";

	return 0;
}