์•Œ๊ณ ๋ฆฌ์ฆ˜

  1. save[0] = 1๋กœ ์ดˆ๊ธฐํ™”
  2. i : 13 ์—์„œ 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];
}