9507번 Generations of Tribbles
18 Dec 2017해당문제는 시간 제한이 2초이므로 다이나믹프로그래밍으로 풀어야한다. 완전 탐색으로 풀 경우 시간이 초과된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <cstdio>
long long koong(int n);
long long num[77];
int main(){
num[0]=1;
num[1]=1;
num[2]=2;
num[3]=4;
int n,t;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
printf("%llu\n",koong(n));
}
return 0;
}
long long koong(int n){
if(num[n] != 0)return num[n];
num[n] = koong(n-1)+koong(n-2)+koong(n-3)+koong(n-4);
return num[n];
}