[백준] 9461번 파도반 수열 (C)

문제 출처

ICPC Asia Pacific Korea Asia Regional - Daejeon 2013 G번

 

문제 주소

백준 9461번 파도반 수열

9461번: 파도반 수열

알고리즘

DP

 

힌트

n번째 삼각형 변의 길이와 이전 삼각형들의 변의 길이와의 관계를 살펴보자

 

 

 

문제 풀이

#include<iostream>
using namespace std;

long long dp[101]={0,1,1,1,2,2,};
int main(){
    int n;
    cin>>n;
    for(int i=6;i<=100;i++){
        dp[i]=(dp[i-1]+dp[i-5]);
    }

    for(int i=0;i<n;i++){
        int tmp;
        cin>>tmp;
        cout<<dp[tmp]<<"\n";
    }
}