[백준][DP]1 2 3 더하기

1. 문제 주소

9095번: 1, 2, 3 더하기

2. 문제

입력받은 정수 n을 1, 2, 3 세 가지 숫자의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하는 문제이다. n=1일 때부터 표현할 수 있는 방법을 나열하면 아래와 같다.

n=1 --- 1 [1]

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

n=3 --- 1+1+1, 1+2, 2+1, 3 [4]

여기서 n=4일때를 표현하면 n=3인 경우에 +1을 하고 n=2인 경우에 +2를 하고 n=1인 경우에 +3을 해주면 된다. 그렇게 되면 나타낼 수 있는 총방법의 수는 1+2+4=7이 된다. 더해지는 가장큰 숫자가 3이므로 n-1부터 n-3까지의 수를 고려해주면 된다.  점화식을 세워보면

$$dp[i]=dp[i-1]+dp[i-2]+dp[i-3]$$

으로 나타낼 수 있으며 이 식을 이용하여 코드를 작성하였다.

3. 소스 코드

1. Bottom-up

#include <iostream>
using namespace std;
 
int dp[11];
 
int main(void)
{
    int t;
    cin >> t;
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;
 
    for (int i = 4; i < 11; i++)
    {
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
    }
 
    while (t--)
    {
        int n;
        cin >> n;
        cout << dp[n] << '\n';        
    }
    return 0;
}

2. Top-down

#include <iostream>
using namespace std;
 
int dp[11];
int topdown(int n)
{
    if (n < 0) return 0;
    if (dp[n]) return dp[n];
    dp[n]= topdown(n - 1) + topdown(n - 2) + topdown(n - 3);
    return dp[n];
}
 
int main(void)
{
    int t;
    cin >> t;
    
    dp[0] = 1;
 
    while (t--)
    {
        int n;
        cin >> n;
        cout << topdown(n) << '\n';        
    }
    return 0;
}