[BOJ] 2749. 피보나치 수 3

문제 원본 : https://www.acmicpc.net/problem/2749

2749번: 피보나치 수 3

#include<iostream>

using namespace std;

long long n[1500000];

int main()
{
	n[0] = 0, n[1] = 1;
	for (int i = 2; i < 1500000; i++)
	{
		n[i] = n[i - 1] + n[i - 2];
		n[i] %= 1000000;
	}

	long long a;
	cin >> a;
	cout << n[a % 1500000] << '\n';
}

• n의 범위가 매우 크므로 일반적인 방법으로는 불가능
• 피사노 주기를 이용해서 해결 가능
• 피사노 주기 참고 : https://comyoung.tistory.com/236