[BOJ알고리즘, C++]#9095_1, 2, 3 더하기, DP

 

#1. 문제

https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

 

---

 

#2. 풀이

 

1. DP, 동적 계획법

https://webddevys.tistory.com/311

[알고리즘]#5_동적 계획법

 

2. 현재 숫자의 -1, -2, -3 숫자의 결과 값을 모두 더하자!

 

1. 총 세 가지 숫자를 통해 현재 숫자를 만들려면, 현재 숫자 - 1, 현재 숫자 -2, 그리고 현재 숫자 - 3 값의 경우의 수를 모두 더해줍니다.
2. 0 ~ 3 까지의 결과 값을 미리 DP 배열에 삽입해 주고, 4부터 주어진 n 값까지 DP를 수행해 주어, 최종적으로 숫자 n에 대한 모든 경우의 수를 출력해 줍니다.

 

---

 

#3. 코드

 

/*
    @문제 : 1, 2, 3의 합으로 숫자 n을 구할 수 있는 경우의 수
    @설명
            1. n에 대한 경우의 수는 dp[n-1] + dp[n-2] + dp[n-3] 과 같다
            2. 점화식, dp[n] = dp[n-1] + dp[n-2] + dp[n-2], when n > 3
*/

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

int T, n;
int dp[11] = {
    0,
    1,
    2,
    4,
};

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

    cin >> T;

    while (T--)
    {
        cin >> n;

        if (n < 4)
        {
            cout << dp[n] << '\n';
            continue;
        }

        for (int i = 4; i <= n; i++)
        {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }
        cout << dp[n] << '\n';
    }

    return 0;
}

 

---