[백준 15624번] 피보나치 수 7 (C++)

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

15624번: 피보나치 수 7

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

const int MOD = 1000000007;
int dp[1000001];
int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    int N;
    cin >> N;

    dp[0]=0; dp[1]=1;
    for(int i=2; i<=N; i++)
    {
        dp[i] =(dp[i-1]+dp[i-2])%MOD; //점화식 % MOD
    }
    cout <<dp[N];
    return 0;
}

흔히 알고 있는 피보나치 점화식을 DP로 풀이한 문제이다.

해당 문제에서 주의할 점은 피보나치수를 MOD로 나눈 나머지를 출력해주는 것이다.

 

이를 위해 매 DP 연산때마다 MOD로 나눠주는 연산을 추가해준다.

마지막 결과값에만 해준다면 부분 점수가 나오게 된다.