파도반 수열 - 9461번 백준

문제

문제 난이도 : 실버 3

문제 분류 : 다이나믹  프로그래밍, 수학(수열)

 

문제 소스 코드

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <queue>
#include <unordered_set>
#include <memory.h>

using namespace std;

long long DP[101];

void Init()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    std::cout.tie(NULL);
}



int main()
{
    Init();
    int n;
    cin >> n;
    DP[0] = 1;
    DP[1] = 1;
    DP[2] = 1;
    DP[3] = 2;
    DP[4] = 2;
    DP[5] = 3;
    DP[6] = 4;
    DP[7] = 5;
    DP[8] = 7;
    DP[9] = 9;
    for (int i = 0; i < n; i++) {
        int Tmp;
        cin >> Tmp;
        for (int j = 5; j < Tmp; j++) {
            DP[j] = DP[j - 2] + DP[j - 3];
        }
        cout << DP[Tmp - 1] << "\n";

    }
}