[Algorithm]Baekjoon 15989번 :: 1,2,3 더하기 4

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

15989번: 1, 2, 3 더하기 4

 
int t, n;
vector<int> answers;
int dp[10001][4] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> t;
 
    int maxNum = 0;
 
    while (t--)
    {
        cin >> n;
 
        answers.push_back(n);
        maxNum = max(maxNum, n);
    }
 
    dp[1][1] = dp[2][1] = dp[2][2] = dp[3][1] = dp[3][2] = dp[3][3] = 1;
 
    for (int i = 4; i <= maxNum; ++i)
    {
        dp[i][1] = dp[i - 1][1];
        dp[i][2] = dp[i - 2][1] + dp[i - 2][2];
        dp[i][3] = dp[i - 3][1] + dp[i - 3][2] + dp[i - 3][3];
    }
 
    for (int i = 0; i < answers.size(); ++i)
    {
        cout << dp[answers[i]][1] + dp[answers[i]][2] + dp[answers[i]][3] << endl;
    }
}
 

 

중복되지 않으면서 1,2,3을 이용한 모든 경우의수를 구해야 하는 문제이다.

예를들어 3을 구성할 때, (1,2) 와 (2,1)은 같은 경우의 수로 취급한다.

그렇기때문에 숫자를 오름차순으로 점점 붙여나가는 식으로 생각하면 겹치지 않고 순수하게 새로운 경우의수들을 붙여나갈 수 있다.