백준/실버

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

게임개발기원 2023. 12. 3. 16:24

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

 

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

혁진이는 알고리즘 문제를 만들라는 독촉을 받아 스트레스다. 하지만 피보나치 문제는 너무 많이 봐서 지겹기 그지없다. 그러나 문제를 만들 시간이 없는 혁진이는 피보나치 문제를 응용해서

www.acmicpc.net

#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로 나눠주도록 하였으므로 매계산마다 이를 잊으면 안된다.