[백준/C++] 9095번: 1,2,3 더하기 (DFS/DP)

 

1) DFS (모든 조합 체크)

 

#include<iostream>
using namespace std;

int test_case, N;
int cnt = 0;
void solve(int sum) {

	if (sum == N) {
		cnt++;
		return;
	}
	if (sum > N) return;
	for (int i = 1; i <= 3; i++) {
		solve(sum+i);
	}
}

int main() {
	cin >> test_case;

	for (int i = 0; i < test_case; i++) {
		cin >> N;
		solve(0);
		cout << cnt << endl;
		cnt = 0;
	}


	return 0;
}

 

2) DP (점화식 도출)

 

각 숫자가 나올 수 있는 경우의 수를 계산하면 dp[n] = dp[n-3] + dp[n-2] + dp[n-1] 라는 점화식을 도출할 수 있다.

 

출처: https://blog.naver.com/PostView.nhn?blogId=vjhh0712v&logNo=221470862600

 

#include<iostream>
using namespace std;

int test_case, N;
int cnt = 0;
int dp[12] = { 0, };

int main() {

	dp[1] = 1;
	dp[2] = 2;
	dp[3] = 4;
	cin >> test_case;

	for (int i = 0; i < test_case; i++) {
		cin >> N;
		cnt = 0;
		for (int i = 4; i <= N; i++) {
			dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
		}
		cout << dp[N] << endl;
		
	}


	return 0;
}