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

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

정답률이 64%에 이르는 비교적 쉬운 난이도의 문제이다.
만약 조건에서 n이 1,2,3의 합이 아닌 더욱 큰 범위까지 이른다면 조금 더 어려워지지 않았을까 싶다.


문제를 보면서 dp를 생각했었는데 4까지의 합을 구할 때 3까지의 합에서 1을 더해주는 방법을 생각하게 되었다. 

그런데 3까지의 합에서 1을 더해주는 것으로 모든 경우를 구할 수 없어서 고민을 했다.


4일 때는 3까지 구한 값에서 '3가지'의 경우가 더 생기고, 5일 때는 4까지 구한 값에서 '6가지'의 경우가 더 생겨서 고민을 하다가 문제의 조건이 1,2,3의 합인 것을 보고 바로 해결할 수 있었다.


이 문제의 포인트는 1,2,3의 합으로 이루어진 경우를 생각하는 것이다.

즉 n 번째에서 1,2,3의 합으로 이루어진 경우는
n-1 번째에서 각각의 값에 1을 더하는 경우
n-2 번째에서 각각의 값에 2를 더하는 경우
n-3 번째에서 각각의 값에 3을 더하는 경우로 나타낼 수 있다.

#include <iostream>
#include <vector>
using namespace std;
 
int main(){
    int n,testCase;
    cin>>testCase;
    
    for(int t=0;t<testCase;t++){
        cin>>n;
        
        int dp[11]={0};
        dp[1]=1, dp[2]=2, dp[3]=4;
        
        for(int i=4;i<=n;i++)
            dp[i]=dp[i-3]+dp[i-2]+dp[i-1];
        
        cout<<dp[n]<<endl;
    }
    return 0;
}