[백준] 9461 파도반 수열 C++ (DP)

📌백준 9461 파도반 수열
https://www.acmicpc.net/problem/9461

---

d[1] = 1
d[2] = 1
d[3] = 1
d[4] = 2
d[5] = 2

으로 정해주고,
6번째부터 규칙이 시작된다.
d[6] = 3
d[7] = 4
d[8] = 5
d[9] = 7
d[10] =9
...

N번째	1	2	3	4	5	6	7	8
변 길이	1	1	1	2	2	3	4	5

여기서 규칙을 알 수 있는데,
d[6] = 1+2 = d[1] + d[5] = 3
d[7] = 1+3 = d[2] + d[6] = 4
d[8] = 1+4 = d[3] + d[7] = 5

점화식을 만들어보면 아래와 같다.
d[N] = d[N-5] + d[N-1]

---

#include<iostream>
using namespace std;

int main()
{

    int T,N;
    cin>>T;
    long long dp[101];

    while(T--)
    {
        scanf("%d",&N);

        dp[1] = 1;
        dp[2] = 1;
        dp[3] = 1;
        dp[4] = 2;
        dp[5] = 2;

        for(int i=6; i<=N; i++)
        {
            dp[i] = dp[i-1] + dp[i-5];
        }
        cout<<dp[N]<<"\n";
    }
}