백준 9095 1, 2, 3 더하기 - C++

 

 

접근

해당 문제는 DP로 푸는 방법과 모든 경우의 수를 구해서 푸는 방법이 있다.

먼저, DP로 푸는 방법은 다음과 같다.

해당 문제는 어떠한 N을 1,2,3의 합으로만 구해야 한다.

 

N은 4이상이고 10이하의 경우

N은 N-1의 경우의 수 +1, N-2의 경우의 수 +2, N-3의 경우의 수 +3을 하게 되면 N이 가질 수 있는 경우의 수가 나오게 된다.

즉 N이 가질 수 있는 경우의 수는 (N-1의 경우의 수) + (N-2의 경우의 수) + (N-3의 경우의 수) 가 된다.

코드는 다음과 같다.

#include <iostream>
using namespace std;
int dp[11];

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

 

마지막으로 모든 경우의 수를 구하면서 N을 만들 수 있는 방법의 수를 계산하면 된다.

 

N을 만들기 위해 

각 자릿수는 1 또는 2또는 3이 오기 때문에 3의 N제곱에 해당하는 경우의 수가 올 수 있다.

자릿수는 최대 N개가 될 수 있다. N이 3일 경우 1+1+1이 될 수 있기 때문에

 

#include <iostream>
using namespace std;
int N, result;
int re(int sum){
    if(sum == N) return 1;
    if(sum > N) return 0;
    
    for(int i=1; i<=3; i++){
        result += re(sum+i);
    }
    return 0;
}

int main(){
    int total;
    cin >> total;
    for(int i=0; i<total; i++){
        cin >> N;
        result = 0;
        re(0);
        cout << result << '\n';
    }
    return 0;
}