백준 9711번 C++

백준 9711번 피보나치

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

9711번: 피보나치

정답 코드

#include <iostream>
using namespace std;

int T, P, Q;
long long dp[10001]={0,1,1,};

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> T;
	for (int i = 1; i <= T; i++) {
		cin >> P >> Q;
		dp[1] = 1;
		dp[2] = 1;
		for (int j = 3; j <=P; j++) {
			dp[j] = (dp[j - 1] + dp[j - 2]) % Q;
		}
		cout << "Case #" << i << ": " << dp[P] % Q << '\n';
	}
	return 0;
}

문제 풀이

기존의 재귀 함수 방식으로 피보나치를 풀면 시간초과가 발생할 것 같아서 dp를 이용하여 풀었습니다.