[C++][백준 9095] 1, 2, 3 더하기 (DP)

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

풀이

일단 그냥 무턱대고 값을 구해보면

dp[1] = 1

dp[2] = 2

dp[3] = 4

dp[4] = 7

dp[5] = 13

으로, 규칙성을 발견할 수 있다

dp[n] = dp[n - 1] + dp[n - 2] + dp[n - 3]과 같은 점화식을 찾을 수 있다

 

왜 성립하는지는 모르고 일단 정답은 맞췄는데

5를 만드는 경우의 수를 구할 때

4를 만드는 모든 경우의 수에 +1를 해주면 5를 만들 수 있고

3을 만드는 모든 경우의 수에 +2를 해주면 5를 만들 수 있고

2를 만드는 모든 경우의 수에 +3을 해주면 5를 만들 수 있다

(4 이상의 차이부터는 하나의 숫자만 더해서 목표 숫자에 도달할 수 없음)

따라서 4, 3, 2를 만들 수 있는 모든 경우의 수를 더해주면 그것이 곧 5를 만들 수 있는 모든 경우의 수가 되는 것이다

맨 뒤에 숫자를 더하면 해당 숫자가 다른 위치에 오는 경우의 수도 발생하지 않나 싶었는데, 2 나 3이 맨 뒤에 가는 경우는 n - 2나 n - 3에서 처리되고, 중간에 들어가는 경우는 n - 1의 경우의 수에서 처리되는 것을 확인할 수 있었다

 

제출 코드

#include <iostream>
using namespace std;

int dp[12];

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

    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;
    for (int i = 4; i < 12; i++)
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];

    int t, n;
    cin >> t;
    while(t--)
    {
        cin >> n;
        cout << dp[n] << '\n';
    }
}