(9461)(DP) 파도반 수열

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

풀이

---

파도반 수열은 피보나치 수열과 어느정도 닮은 부분이 있는데 삼각형을 나선으로 계속 추가하는데 가장 긴 변에 삼각형을 계속 추가한다. 이러한 특성 때문에 처음에

긴변이 생기기 전까지 변의 길이는 p(1)    =    p(2)    =    p(3)    =    1 로 동일하다.

초기 값을 제외하고 이후의 값들의 규칙을 찾아보면 

p[i]    =    p[i-1] + p[i-5]; 와 같은 형태를 띄는 것을 차례대로 삼각형을 추가하며 그려보면 어렵지 않게 알 수 있다.

또는 p[i]    =    p[n-2] + p[n-3];과 같은 규칙도 띈다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
int main() {
    long long int dp[101] = { 0 };
    int T, N;
    
    scanf("%d", &T);
    
    dp[1] = 1;
    dp[2] = 1;
    dp[3] = 1;
    dp[4] = 2;
    dp[5] = 2;
 
    for (int i = 1; i <= T; i++) {
        scanf("%d", &N);
        for (int j = 6; j <= N; j++) {
            dp[j] = dp[j - 1] + dp[j - 5];
        }
        printf("%lld\n", dp[N]);
    }
    
    return 0;
    
}