백준 c++2749 "피보나치 수 3" -PlusUltraCode-

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

 

 

 

 

 

 

 

[필자사고]

https://www.acmicpc.net/problem/9471 << 선행해야 되는 문제

 

이 문제는 피사노 주기를 알면 쉽게 풀 수 있는 문제이다.

 

피사노 주기의 특징은 k(10n) = 15×10(n-1) 와 같은 특징이 있따.

 

예를들어 1000000으로 나눠야 되는 상황이 있으면

 

k(10^6) = 15x10(10^5) 의 공식이 성립하여

 

k의 값은 1500000가 된다.

 

즉 100만으로 나누게 될 경우 15만마다 주기가 생긴다는 점이다.

 

이 문제의 N의 값은 매우 크기 때문에 모든 값을 다 담게 되면 메모리 초과가 생길것이다.

 

여기서 핵심은 15만 마다 주기가 반복되므로 15만의 크기의 배열만 확인하면 문제를 쉽게 해결할 수 있따.

 

[소스 코드]

#include <iostream>
#include <vector>


using namespace std;

long long N;
vector<long long> Dp;

//k(10n) = 15×10(n-1)

void Input() {
	cin >> N;
	Dp.resize(1500001);
	Dp[0] = 0;
	Dp[1] = 1;
	Dp[2] = 1;
}

void Solve() {
	for (int i = 3; i <=1500000; i++) {
		Dp[i] = Dp[i - 1] + Dp[i - 2];
		Dp[i] %= 1000000;
	}
}

int main(void) {
	Input();
	Solve();
	cout << Dp[N%1500000];

}