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

코드

#include <iostream>

using namespace std;
typedef long long ll;

const int mod = 1000000007;
ll n, dp[52],res[52];


int main() {
    cin >> n;
    dp[1] = 2;
    dp[2] = 2;
    // 재귀가 늘어나는 수열은 피보나치 규칙을 따르고 있다.
    for(int i = 3; i < n + 1; i++) {
        dp[i] = (dp[i - 1] + dp[i - 2])%mod;
    }
    res[0] = 1;
    res[1] = 1;
    // 재귀가 늘어난 횟수 증가
    for(int i = 2; i < n + 1; i++) {
        res[i] = (res[i - 1] + dp[i - 1])%mod;
    }

    cout << res[n] << '\n';
    return 0;
}

피보나치 수열을 구할 때, n <= 30일 때는 시간이 얼마 걸리지 않으므로 직접 확인해봤다. 재귀가 늘어나는 방식은 피보나치 수열 규칙을 따르고 있기 때문에 먼저 해당 값을 먼저 구했고, 그 후 정답을 찾는 방식으로 접근했다.