백준 9461번 - 파도반 수열

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

언뜻 보면 어려운 문제처럼 보이는데 규칙만 찾아내면 쉽게 풀 수 있는 문제이다.


9번째 삼각형 (길이가 7)부터 
바로 이전 삼각형과 5번째 전의 삼각형의 길이의 합이 해당 삼각형의 길이인 것을 알면 된다.


n이 입력될 때마다 이를 계속 구하는 작업을 할 필요 없이
미리 100까지의 값을 구하면 되는데, 마지막 100번째 삼각형의 길이는 int 범위를 벗어나기 때문에
long 타입으로 값을 구해서 출력해주면 된다.

#include <iostream>
using namespace std;
 
int main(){
    
    int T,n;
    long dp[101]={0,1,1,1,2,2,3,4,5};
    for(int i=9;i<=100;i++)
        dp[i]=dp[i-5]+dp[i-1];
    
    cin>>T;
    for(int testCase=0;testCase<T;testCase++){
        scanf("%d",&n);
        printf("%ld\n",dp[n]);
    }
    
    return 0;
}