[BOJ] DP 9095번 1, 2, 3 더하기 C++

9095번 1, 2, 3 더하기

📝문제링크 : www.acmicpc.net/problem/9095

 

#include <iostream>
#include <vector>

using namespace std;

void	find_ans(int n, vector<int> &dp)
{
    for (int i = 4; i <= n; i++)
    {
    	dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];
    }
}

int	main(){
    int T, n;
    cin >> T;
    vector<int> dp;

    for (int i = 0; i < T; i++)
    {
        cin >> n;
        dp.assign(n + 1, 0);
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        find_ans(n, dp);
        cout << dp[n] << '\n';
    }
    return (0);
}

 

점화식 : $ dp[n] = dp[n - 3] + dp[n - 2] + dp[n - 1] $

 

덧셈이 1, 2, 3으로만 구성되어 있기 때문에 임의의 수 n 에 대한 덧셈식은 + 1 로 끝나거나 + 2 로 끝나거나 + 3으로 끝나는 경우 밖에 없다. 따라서 n - 3, n - 2, n - 1 번째 수를 만드는 가지수를 더해주면 n 의 계산식을 만드는 가지수가 된다. 

 

문제를 풀지 못한 이유.
n = 5 라면, 2 + 3으로 나누고, 2 를 또 1 + 1로 나누고 3은 2 + 1로 나누는 것처럼 쪼개서 내려가야 하나 복잡하게 생각했음.