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

🏆 목차.

1. 문제
2. 코드
3. 풀이

 

🛒 문제

 

백준 9095번 1, 2, 3 더하기

 

🎨 코드

 

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int T;
    cin >> T;

    for (int i = 0; i < T; i++)
    {
        int n;
        cin >> n;
        vector<int> dp(n + 1, 0); 

        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        for (int j = 4; j <= n; j++) 
        {
            dp[j] = dp[j - 1] + dp[j - 2] + dp[j - 3];
        }
        cout << dp[n] << endl;
    }
    return 0;
}

 

🎯 풀이

 

이번 문제는 다이내믹 프로그래밍(DP)을 이용해 푸는 문제로 점화식만 떠오르면 쉽게 풀 수 있지만 잘 생각 안 나서 문제입니다..

 

이번에도 이해하기 쉽게 그림으로 설명하겠습니다.

 

1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제로 덧셈의 마지막에는 무조건 1 또는 2 또는 3이 오게 됩니다.

 

1, 2, 3의 합 방법의 수

세 가지 경우의 수를 모두 더할 경우

DP [N] = DP [N-1] + DP [N-2] + DP [N-3]이 됩니다.

 

위 코드에 보면 DP [0]은 1로 정의했는데 아무것도 더하지 않는다는 경우도 포함시키기 때문입니다.

 

2는 1+1, 2로 방법의 수가 2개

3은 1+1+1, 2+1, 1+2, 3으로 방법의 수가 4개가 되어 앞서 정의해 두었고 

이후부터는 위 규칙을 이용하여 코드를 작성하면 풀 수 있습니다.