[BOJ]90951,2,3プラス(ダイナミックプログラミング)

1.質問

2.アイデア

3.解法

1)使用110 GHT⭕-繰り返し文

#include <iostream>
using namespace std;

int addition[11] = { 0,1,2,4};

int solve(int n)
{
	if (addition[n]) return addition[n];
	else return addition[n] = solve(n - 1) + solve(n - 2) + solve(n - 3);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int T; // Testcase 수
	int n;

	cin >> T;

	solve(10); // 가능한 모든 n에 대해서 미리 구하여둠
	while (T--)
	{
		cin >> n;
		cout << addition[n] << '\n';
	}
	return 0;
}

2)110 GHT⭕-再使用

#include <iostream>
using namespace std;

int DP[12] = { 0 };

int recursive(int i) {
	if (i == 1) return 1;
	if (i == 2) return 2;
	if (i == 3) return 4;
	DP[i] = recursive(i - 1) + recursive(i - 2) + recursive(i - 3);

	return DP[i];
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int testcase; cin >> testcase;
	int max_prev_n = 3, cur_n;

	DP[0] = 0;
	DP[1] = 1; DP[2] = 2; DP[3] = 4;

	while (testcase--) {
		cin >> cur_n;
		
		if (max_prev_n < cur_n) recursive(cur_n);

		cout << DP[cur_n] << '\n';

		if (max_prev_n < cur_n) max_prev_n = cur_n;
	}
	return 0;
}