💡 다이나믹 프로그래밍
Memory 2060KB Time 16ms Code Length 386B
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <string.h>
using namespace std;
int dp[10004];
int T;
int main() {
cin >> T;
while (T--) {
int n;
cin >> n;
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= 3; i++) { // 각 숫자마다 반복
dp[i]++;
for (int j = i + 1; j <= n; j++) { // i 보다 큰 dp 테이블 생성하기
dp[j] += dp[j-i];
}
}
cout << dp[n] << "\n";
}
}
이 코드는 T번의 테스트 케이스를 입력 받고, 각 테스트 케이스마다 n을 입력 받는다. 그 후, 1부터 3까지의 숫자에 대해 dp 배열을 초기화하고, 각 숫자마다 반복하면서 dp 배열을 업데이트한다. 이때, 현재 숫자보다 큰 숫자들에 대해 dp 값을 갱신하는데, 각 숫자는 이전 숫자들의 합으로 표현된다. 마지막으로 dp[n] 값을 출력한다.
