💡 다이나믹 프로그래밍
Memory 39200KB Time 40ms Code Length 469B
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
31
32
33
34
#include<iostream>
#define MAX 1000001
#define MOD 1000000009
using namespace std;
int T;
long long dp[MAX];
void init() {
cin >> T;
}
int dp_F(int r) {
if (r == 0) return 0;
if (dp[r] != 0) {
return dp[r];
}
dp[r] = ((dp_F(r - 1) + dp_F(r - 2)) % MOD + dp_F(r - 3)) % MOD;
return dp[r];
}
int main() {
dp[1] = 1;
dp[2] = 2;
dp[3] = 4;
init();
while (T--) {
int n;
cin >> n;
if (dp[n] == 0) {
dp[n] = dp_F(n);
}
cout << dp[n] << endl;
}
}
이 코드는 다이나믹 프로그래밍을 사용하여 주어진 수열을 계산하는 프로그램이다.
init 함수에서는 변수 T에 테스트 케이스의 개수를 입력받는다.
dp 배열은 각 인덱스에 해당하는 값을 저장하는데, dp_F 함수를 통해 값을 계산하고 저장한다.
dp_F 함수는 재귀적으로 호출되며, 이전 값들을 활용하여 현재 값을 계산한다.
main 함수에서는 초기값을 설정하고, 테스트 케이스의 수만큼 반복하면서 주어진 수열의 값을 출력한다. 만약 해당 값이 이전에 계산되지 않았다면 dp_F 함수를 호출하여 값을 계산하고 출력한다.
