BOJ 9461번 :: 파도반 수열

#문제

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

#작성 코드

#include <cstdio>

int T, N;
long long int memo[101];
long long int pn(int n){
	if( n==1 ) return 1;
	if( n==2 ) return 1;
	if( n==3 ) return 1;
	if( n==4 ) return 2;
	if( n==5 ) return 2;
	if( n==6 ) return 3;
	if( n==7 ) return 4;
	if( n==8 ) return 5;
	
	if( memo[n]!=0 ) return memo[n];
	return memo[n] = pn(n-1)+pn(n-5);
}
int main(){
	scanf("%d",&T);
	for(int i=0; i<T; i++){
		scanf("%d", &N);
		printf("%lld\n", pn(N));
	}
} 

##

P(1) ~ P(6)까지는 주어진 수열을 그대로 사용하고,

 P(7)부터 P(N) = P(N-1)+P(N-5) 라는 규칙이 생긴다.