[Silver IV] 피보나치 수 7 - 15624

[문제 위치]

https://www.acmicpc.net/problem/15624

[문제 풀이]

이 문제는 DP를 활용한 피보나치 문제이다.

숫자가 매우 커질 수 있으므로 모듈러를 만들어 나누어주어가며 계산해주면 되는 문제이다.

점화식 자체는 피보나치 수열이므로 별다른 특별할 것이 없다.

아래는 이를 코드로 구현한 것이다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define FASTIO ios::sync_with_stdio(false); cin.tie(nullptr);

const int MOD = 1000000007;

int main() {
    FASTIO
    int N;
    cin >> N;
    vector<int> DP(N+1, 0);
    if (N >= 1) DP[1] = 1;
    for (int i = 2; i <= N; i++) {
        DP[i] = (DP[i - 1] + DP[i - 2]) % MOD;
    }
    cout << DP[N];
    return 0;
}