알고리즘
- save[0] = 1로 초기화
- i : 1~3 에서 j : i~m 까지 save[j] += save[j-i] 를 반복
원리
i = 1에서는 1로만 쭉 더한 것(3 = 1 + 1 + 1) 경우만 따짐.
i = 2에서는 1로만 더한 것에 2를 추가한 경우를 따진다.
i = 3에서도 마찬가지.
ex) m = 4일때
i = 1
1 = 1
2 = 1 + 1
3 = 1 + 1 + 1
4 = 1 + 1 + 1 + 1
i = 2
1 = 1
2 = 1 + 1 / 2
3 = 1 + 1 + 1 / 1 + 2
4 = 1 + 1 + 1 + 1 / 1 + 1 + 2 / 2 + 2
i = 3
1 = 1
2 = 1 + 1 / 2
3 = 1 + 1 + 1 / 1 + 2 / 3
4 = 1 + 1 + 1 + 1 / 1 + 1 + 2 / 2 + 2 / 1 + 3
코드
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
#include <iostream>
#include <cstring>
using namespace std;
int n, m;
long long save[10010];
long long dp();
int main() {
cin >> n;
while (n--) {
cin >> m;
cout << dp() << endl;
memset(save, 0, sizeof(save));
}
}
long long dp() {
save[0] = 1;
for (int i = 1; i <= 3; i++)
for (int j = i; j <= m; j++)
save[j] += save[j - i];
return save[m];
}