BOJ 백준온라인져지 2749 피보나치 수 3 풀이

피보나치 수열을 n으로 나눈 나머지는 주기가 있다.

이 주기를 피사노 주기라고 한다.

나는 이 피사노 주기를 알기 전에 우연히 forloop으로 피보나치 수열을 1000만까지 찍었는데 같은수가 계속 출력돼서 주기가 있다는것을 알았다.

그리고 찾아보니 피사노 주기가 있다는것을 알았다.

	#include <cstdio>
	/**
	* https://www.acmicpc.net/problem/2749
	* BOJ 백준온라인져지 2749 피보나치 수 3 풀이
	*/
	int main(){
	unsigned long long N;
	scanf("%lld", &N);
	int *fibonacci = new int[1500001];
	fibonacci[1] = 1;
	for(int i = 2; i <= 1500000; i++){
	fibonacci[i] = (fibonacci[i - 1] + fibonacci[i - 2]) % 1000000;
	}
	printf("%d", fibonacci[N % 1500000]);
	}

view raw BOJ_2749.cpp hosted with ❤ by GitHub