방식 1
#include <stdio.h>
int n, memo[10000];
long long int f(int n)
{
if(n==0) return 1;
if(n==1) return 1;
if(n==2) return 2;
return memo[n]=(f(n-1)+f(n-2)+3*f(n-3))00;
}
int main()
{
scanf("%d", &n);
printf("%d\n", f(n));
return 0;
}
방식 2
#include <stdio.h>
int n, memo[10000];
long long int f(int k)
{
if(k==1) return 1;
if(k==2) return 2;
if(k==3) return 6;
else
{
if(memo[k]==0)
{
if(k%2) memo[k]=(f(k/2)*f(k/2)+f(k/2-1)*f(k/2-1))00;
else memo[k]=(f(k/2)*f(k/2)+2*f(k/2-1)*f(k/2))00;
}
return memo[k];
}
}
int main()
{
scanf("%d", &n);
printf("%lld\n", f(n));
return 0;
}
방식 1로 하면 시간초과여서 방식 2로 했는데 답이 안나오네요
댓글 0