백준 9461번. 파도반 수열(c++) / DP

점화식을 세워서 풀 수 있는 DP문제였다.

DP[n] = DP[n-1]+DP[n-5];

1~5의 DP값은 미리 넣어놓고 이것보다 큰 값의 경우에만 계산해주었다.

 

// 파도반 수열
#include <iostream>
using namespace std;
 
int n, testcase;
long long dp[101] = {0, };
 
void setting()
{
    dp[1] = 1;
    dp[2] = 1;
    dp[3] = 1;
    dp[4] = 2;
    dp[5] = 2;
}
 
int main()
{
    cin>>testcase;
    setting();
    for(int i=0; i<testcase; i++){
        cin>>n;
 
        if(dp[n]!=0){
            cout<<dp[n]<<"\n";
        }else{
            for(int j=5; j<=n; j++){
                dp[j] = dp[j-1]+dp[j-5];
            }
            cout<<dp[n]<<"\n";            
        }
    }
 
    return 0;
}