์๊ณ ๋ฆฌ์ฆ
- save[0] = 1๋ก ์ด๊ธฐํ
- i : 1
3 ์์ j : im ๊น์ง 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
-
-
์ฝ๋
#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];
}