[백준][9461번][DP] 파도반 수열

파도반 수열

https://www.acmicpc.net/problem/9461

<코드>

#include <stdio.h>
 
int main(void){
    int testcase;
    long long Dp[101] = { 1, 1, 1, 1, 2, 2, };
 
    scanf("%d",&testcase);
 
    for (int i = 6; i <= 100; i++)
        Dp[i] = Dp[i - 1] + Dp[i - 5];
 
    while (testcase--){
        int n;
        scanf("%d", &n);
        printf("%lld\n", Dp[n]);
    }
 
}

<문제 푼 방법>

1. 이 문제 같은 경우는 초기값들을 제외하고 나머지 값들이 규칙을 가지고 변한다.

2. 그 규칙은 6번 이상의 숫자부터 Dp[i] = Dp[i-1] + Dp[i-5] 라는 규칙을 가지고 변하기 때문에 이 규칙만 발견한다면 쉽게 구할 수 있다.