💡 다이나믹 프로그래밍
Memory 5016KB Time 0ms Code Length 463B
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
28
29
30
#include<stdio.h>
#define min(x,y) x>y?y:x
using namespace std;
int memo[1000001] = {0, 1,2,4};
int dp(int n) {
if (n == 0 || n == 1 || n==2 || n==3)
return memo[n];
for (int i = 4; i <= n; i++) {
if (memo[i])continue;
memo[i] = memo[i - 3] + memo[i - 2] + memo[i - 1];
}
return memo[n];
}
int main() {
int tc;
scanf("%d", &tc);
getchar();
for (int T = 0; T < tc; T++) {
int n;
scanf("%d", &n);
getchar();
printf("%d\n", dp(n));
}
}
이 코드는 다이나믹 프로그래밍을 사용하여 피보나치 수열을 계산하는 프로그램이다. 먼저 memo 배열에 초기값을 설정해놓고, dp 함수를 통해 n번째 피보나치 수를 계산한다. dp 함수는 n이 0, 1, 2, 3일 때는 미리 계산된 값을 반환하고, 그 외의 경우에는 이전 값들을 활용하여 값을 계산한다. 메인 함수에서는 테스트 케이스의 개수를 입력받고 각각의 테스트 케이스에 대해 dp 함수를 호출하여 결과를 출력한다.
