백준 알고리즘 9711번 : 피보나치(100%에서 실패)

링크

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

문제

피보나치 수열은 아래와 같이 표현된다.

1, 1, 2, 3, 5, 8, 13, 21, 34, ...

각 숫자는 앞의 두 숫자의 합으로 나타내는 것을 알 수 있다.

P와 Q 그리고 n이 주어질 때, P번째 피보나치 숫자를 Q로 나눈 나머지를 구하여라.

입력

첫 번째 라인에는 정수 T개의 테스트 케이스가 주어진다.

각 테스트 케이스는 정수 P와 Q가 주어진다.

출력

각 테스트 케이스마다 "Case #x: M" 형식으로 출력한다.

x는 테스트 케이스 번호(1부터 시작), M은 P번째 피보나치 숫자를 Q로 나눈 나머지이다.

예제 입력 및 출력

100%에서 틀린 코드(C++)

재풀이 예정 ㅠㅠ

#include <iostream>
#include <deque>
#include <vector>
#include <queue>
#include <algorithm> 
#define max 10001
#define lli long long int
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) 
using namespace std;

lli dp[max] = {1,1,2};

int main(){
  fastio;
  int tc;
  cin >> tc;
  for(int i = 1; i <= tc; i++){
    int p,q;
    cin >> p >> q;
    if(p == 1 && q == 1){
      printf("Case #%d: 0\n",i);
      continue;
    }
    for(int i = 2; i <= p; i++){
      dp[i] = (dp[i - 1] + dp[i - 2]) % q;
    }
    printf("Case #%d: %lld\n",i, dp[p - 1]);
  }
  return 0;
}