파도반 수열

이처럼 계속 증가하는 모양을 가지는 형태가 있다.

테스트 케이스 T가 주어졌을 때,

 

P(1) = 1

P(2) = 1

P(3) = 1

P(4) = 2

...

P(9) = 7

P(10) = 9 일때

P(n)을 구하시오. ( 1<= n <= 100 )

#include <stdio.h>
 
long long int ans;
 
int padovan(int n)
{
 if(n == 1) return 1;
 else if(n == 2) return 1;
 else if(n == 3) return 1;
 else if(n == 4) return 2;
 else if(n == 5) return 2;
 else if(n == 6) return 3;
 else if(n == 7) return 4;
 else if(n == 8) return 5;
 else if(n == 9) return 7;
 else if(n == 10) return 9;
 
 
 else
 return padovan(n-1) + padovan(n-5);    
}
 
 
int main()
{
 int T,n;
 
 scanf("%d",&T);
 
 while(T > 0)
 {
  scanf("%d",&n);
         
  ans = padovan(n);   
  
  printf("%lld\n",ans);
 
  T--;
 } 
 
return 0; 
}
 
 

결국 파도반 수열은 P(n) = P(n-1) + P(n-5)이다.

처음엔 다음과 같이 재귀 함수를 통한 값을 구하려고 하였지만,

n의 값을 77정도만 설정해도 시간이 2초정도 걸리고

88을 넣으면 계산을 못해내었다.

그래서 다르게 생각을 한 결과

prefix sum방식과 비슷하게 처음에 모든 값을 다 구해 놓는 방법을 쓰면 된다는 것을 알았다.

 
#include <stdio.h>
 
long long int result[100]={0,};
long long int N[101]={0,};
 
int main(){
    int T,i;
    scanf("%d",&T);
 
    int insert;
    N[0]=1;
    N[1]=1;
    N[2]=1;
    N[3]=2;
    N[4]=2;
    N[5]=3;
    N[6]=4;
    N[7]=5;
    N[8]=7;
    N[9]=9;
    
    for(i=10;i<101;i++)
    {
        N[i]=N[i-1]+N[i-5];
    }
 
    for(i=0; i<T; i++){
        scanf("%d",&insert);
        result[i]=N[insert-1];
    }
    for(i=0;i<T;i++){
        printf("%lld\n",result[i]);
    }
 
}
 

재귀호출을 적재적소에 쓰면 좋은 코딩도 있지만, 괜히 재귀를 이용한 시간 복잡도의 증가와 메모리 낭비를 하지말자.