점화식을 구해보자

일단 가장 첫번째로 점화식이 하나 있다.
연구를 하다 보면 이것에 규칙이 있다는것을 알게될 것이고 그게 곧 점화식으로 표현이 된다.
다이나믹 프로그래밍 이기 때문이다

aₙ₊₁ = aₙ₋₁ + aₙ₋₅

이런 점화식이 있지만 눈치가 빨랐다면 의문이 생길것이다.

1부터 5까지는 어케 구함?

그러므로 1부터 5까지는 수시로 값을 집어 넣어 줘어야 한다.

개인적으로 말하지만 실버3는 풀이는 거의 다 간단하지만 생각이 오래 걸리는거 같다.

코드

#include <vector>
#include <iostream>
using namespace std;

int main()
{
    long long test_case;
    vector<long long> v;
    
    v.push_back(1);
    v.push_back(1);
    v.push_back(1);
    v.push_back(2);
    v.push_back(2);

    for (int i = 5; i < 100; i++) {
        v.push_back(v.at(i - 5) + v.at(i - 1));
    }

    cin >> test_case;
    for (int i = 1; i <= test_case; i++) {
        long long n;
        cin >> n;
        cout << v.at(n - 1) << "\n";
    }
}

이 코드를 쓰게되면 맞는다.