[Math] 9461번 - 바도반 수열(36일차)

#include <iostream>

using namespace std;

int main(){
    //문제 개수
    int t;
    cin >> t;

    while(t--){
        //찾고자 하는 수열의 순서
        int n;
        cin >> n;
        //각 수열의 값을 저장하는 dp
        int *dp = new int[n+1];
        //1~n까지 수열의 값을 연산
        for(int i=1; i<n+1; i++){
            //나선 하나를 생성하기 위해서는 삼각형 3개가 필요하므로
            //1~3번째까지는 수열의 값은 1
            if(i<=3){
                dp[i] = 1;
            }
            //처음 생성된 나선을 기반으로 새로운 나선을 생성하기 위해서는 삼각형 2개가 필요하므로
            //4~5번째까지 수열의 값은 2
            else if(3 < i  && i <= 5){
                dp[i] = 2;
            }
            //이후로는 나선을 생성하는데 삼각형 1개만 있으면 되므로
            //n-1번째 수열의 값과 n-5번째 수열의 값의 합을 취함
            else{
                dp[i] = dp[i-1] + dp[i-5];
            }
        }
        //목표 수열의 값 출력
        cout << dp[n];
    }
}