파도반 수열 (DP)

------------------------------------------------------------------------------------------------------------------------------------------------------------------------

#include<stdio.h>

#define n 101

long long dp[n] = { 0,1,1,1,2,2 };

void podo()

{

for (int i = 6; i <= 100; i++)

{

dp[i] = dp[i - 5] + dp[i - 1];   //  <-- 파도반 수열의 엔진

}

}

int main()

{

podo();

int arr[100] = { 0 };

int test;

scanf("%d",&test);

for (int i = 1; i <= test; i++)

scanf("%d",&arr[i]);

for (int i = 1; i <= test; i++)

printf("%lld\n",dp[arr[i]]);

return 0;

}

파도반 수열은 규칙이 딱 있다. 

dp[i] = dp [i - 5] + dp[i - 1]

예를 들어서  8번째 파도반 수열의 수를 구한다면  3번째 수 + 7번째 수를 더해주면 된다,