[백준 17175번] 피보나치는 지겨웡~ (C++)

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

17175번: 피보나치는 지겨웡~

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

int N;
int dp[51];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N;
    dp[0]=dp[1]=1;

    for(int i=2; i<=N; i++)
    {
        dp[i] = (1 + dp[i-2] + dp[i-1])%1000000007; //카운팅 + 나눠주기
    }

    cout << dp[N];

    return 0;
}

 

기존 피보나치 수열 점화식에 호출 횟수 카운팅을 위한 + 1을 추가한 문제이다.

그리고 해당문제에서 너무 큰수을 대비하기 위해 1000000007로 나눠주도록 하였으므로 매계산마다 이를 잊으면 안된다.