DP_백준_파도반 수열_9461

이 문제와 같이 그림이 있으면 그림으로 점화식을 유추할 수있다.

1. 정의 : 정삼각형의 변의 길이

2. 점화식 : dp[N-1] + dp[N-2]

3. 초기화 : 코드참조

#include <iostream>
using namespace std;
 
int main() {
    int count;
    cin >> count;
    for (int a = 0; a < count; a++) {
        long long dp[101];
        int n;
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 1;
        dp[3] = 2;
        dp[4] = 2;
        //Initialize        
 
        cin >> n;
        for (int i = 5; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 5];
        }
        //Calculate
        cout << dp[n - 1] << endl;
    }
}