[PS][DP]/[BOJ][9095][1, 2, 3 더하기]

boj9095.cpp

#include <iostream>

using namespace std;

int dp[11];

int main(void) {
	dp[1] = 1;
	dp[2] = 2;
	dp[3] = 4;
	for (int i = 4; i <= 10; i++) {
		dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
	}
	int n=0,m=0;
	cin >> n;
	while (n--) {
		cin >> m;
		cout << dp[m] << "\n";
	}
	
	return 0;
}

//모든 경우의 수를 하나씩 세는 방법

#include <iostream>

using namespace std;

int n = 0;
int arr[100] = { 0 };
int ans = 0;
void recur(int curr, int sum) {
	if (sum == 0) {
		ans++;
		/*for (int i = 0; i < curr; i++) {
			cout << arr[i] << ' ';
		}
		cout << "\n";*/
		return;
	} 
	for (int i = 1; i <=3; i++) {
		if (i <= sum) {
			arr[curr] = i;
			recur(curr + 1, sum - i);
		}
	}
}
 
 int main(void) {
	int t = 0;
	cin >> t;
	while (t--) {
		cin >> n;
		recur(0, n);
		cout << ans << "\n";
		ans = 0;
	}
	return 0;
}

//int형 return 값을 갖는 recur함수 풀이

#include <iostream>

using namespace std;

int n = 0;
int arr[100] = { 0 };
int recur(int sum) {
	int ret = 0;
	if (sum == 0) return 1;
	for (int i = 1; i <= 3; i++) {
		if (i <= sum) {
			ret += recur(sum - i);
		}
	}
	return ret;
}
 
 int main(void) {
	int t = 0;
	cin >> t;
	while (t--) {
		cin >> n;
		cout << recur(n) << "\n";
	}
	return 0;
}