백준 BOJ 9711 피보나치

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

9711번: 피보나치

문제 해설

P번째 피보나치 숫자를 Q로 나눈 나머지를 출력하는 문제다.

 

P의 값이 최대 10,000 이다.10,000번째 피보나치 수를 구하면 int 자료형의 표현 범위를 벗어나게 된다.그래서 Q(20억 이하의 자연수)로 나눈 나머지를 구하도록했다.

 

DP를 이용해 P번째 피보나치 수를 구하는 시간복잡도는 O(P)이다.P가 최대 10,000이므로 단순히 구해도 될 것처럼 보인다.이 문제는 그냥 다 구해도 된다.(더 빠른 연산은 https://daan.tistory.com/45을 참고할 수 있다.)

 

#include <iostream>
#define fio cin.tie(0)->sync_with_stdio(0)

using namespace std;

#include <vector>
int dp_pth_q(int P, int Q){
	vector<long long>fibo(P+1, 0);
	fibo[1] = 1; fibo[2] = 1;
	for(int i=3; i<=P; i++){
		fibo[i] = fibo[i-1] + fibo[i-2];
		fibo[i] %= Q;
	}
	return fibo[P]%Q; 
}
int main() {
	fio;
	int T; cin >> T;
	for(int tc=1; tc<= T; tc++){
		int P, Q; cin >> P >> Q;
		int ans = dp_pth_q(P, Q);
		cout <<"Case #"<< tc <<": "<< ans<<'\n';
	}

	return 0;
}