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

www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

브루트 포스(완전 탐색) 또는 DP 둘다 이용해서 풀 수 있는 문제

브루트 포스로 해결할 경우 DFS를 통해 1, 2, 3을 이용하여 n을 나타내는 모든 경우의 수를 구하면 됩니다.

DP를 통해 해결할 경우 다음과 같은 규칙을 찾아내면 됩니다.

1을 표현할 수 있는 경우 : 1 -> 1가지

2를 표현할 수 있는 경우 : 1+1, 2 -> 2가지

3을 표현할 수 있는 경우 : 1+1+1, 1+2, 2+1, 3 -> 4가지

따라서 다음과 같은 점화식을 도출해낼 수 있습니다

dp[n] = dp[n - 2] + dp[n - 1]

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int answer;

void DFS(int sum, int n) {
	if(sum > n) return;
	if(sum == n) answer++;
	for(int i = 1; i <= 3; i++) {
		DFS(sum + i, n);
	}
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

	int T;
	cin>>T;
	for(int i = 0; i < T; i++) {
		int n;
		cin>>n;
		DFS(0, n);
		cout<<answer<<"\n";
		answer = 0;
	}
}

 

#include <iostream>
using namespace std;

int dp[11];

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin>>t;
    
    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];
    }
    
    while(t--) {
        int n;
        cin>>n;
        cout<<dp[n]<<"\n";
    }
}