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

---

0. 문제

 

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

 

1. 아이디어

 

1) 정수 n에 대해서 1, 2, 3의 합으로 나타낼 수 있는 방법의 수는 n-1+1, n-2+2, n-3+3 을 하는 방법의 수와 같다.

 

2. 소스코드

 

#include <iostream>
int main()
{
    int T;
    std::cin >> T;
    for (int i = 0; i < T; i++)
    {
        int n, result;
        std::cin >> n;
        if (n == 1) result = 1;
        else if (n == 2) result = 2;
        else if (n == 3) result = 4;
        else
        {
            int* dp = new int[n + 1];
            dp[1] = 1; dp[2] = 2; dp[3] = 4;
            for (int i = 4; i <= n; i++)
                dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
            result = dp[n];
            delete[] dp;
        }
        std::cout << result << '\n';
    }
}

 

3. 결과

 

 

4. 피드백

 

---