백준 9461번

파도반 수열 문제입니다.

1, 1, 1, 2, 2, 3, 4, 5, 7, 9 ...

뭔가 규칙이 있을것만 같은 배열입니다. 실제로 규칙을 찾아보면 6번째값인 3부터 규칙을 찾을 수 있습니다.

i번째 파도반 수열의 값은 i-1번째 값 에 i-5번째 값을 더하면 나옵니다.

이전문제에 시간을 쏟은걸 생각하면 너무 쉽게 풀린 문제입니다.

#include <cstdio>
 
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
 
        int fixed[6] = { 1, 1, 1, 2, 2, 3 };
        int* dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            if (i < 6) {
                dp[i] = fixed[i - 1];
            }
            else {
                dp[i] = dp[i - 1] + dp[i - 5];
            }
        }
 
        printf("%d\n", dp[n]);
    }
}