[백준 9711번] 피보나치 (C++)

문제링크 : https://www.acmicpc.net/problem/9711

9711번: 피보나치

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int T, P, Q;
ll dp[10001]; //합산시 int 범위 초과

int func(int p, int q)
{
    dp[1]=1;
    dp[2]=1;

    for(int i=3; i<=p; i++)
    {
        dp[i] = dp[i-1]+dp[i-2]; //피보나치
        dp[i] %= q;
    }
    return dp[p]%q;
}
int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> T;
    for(int i=1; i<=T; i++)
    {
        cin >> P >> Q;
        cout <<"Case #"<< i <<": "<< func(P, Q)<<"\n";
    }
    return 0;
}

 

간단한 피보나치 배열 규칙을 사용한 dp 문제이다.

수의 범위가 20억까지 올 수 있으므로 합산시에 int 범위를 초과하는 경우가 발생한다.

따라서 이를 위해 dp식을 long long으로 선언해준다.