[백준] 9095번 : 1,2,3 더하기

#include <iostream>
#include <vector>

using namespace std;

int t,n; // 테스트케이스 개수, 1 2 3합으로 나타낼 정수 n
vector<int> dp(1001); // 정수를 1,2,3의 합으로 나타내는 방법

int main()
{
    dp[1]=1; 
    dp[2]=2;
    dp[3]=4;
        
    for(int i=4; i<11; i++){
    dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
    }
    
    //입력
    cin>>t;
    
    while(t--){
        cin>>n;
        cout<<dp[n]<<'\n';
    }
    return 0;
}

-dp 배열이 12개를 다 구해놓을 필요가 있나?

+하나의 입력값에 대해 하나의 출력값이 나와도 괜찮음.

+점화식을 처음에 찾는게 어려웠다. 1,2,3,4의 경우를 먼저 생각해보면
dp[1] = 1 //1
dp[2] = 2 // 1+1, 2
dp[3] = 4 // 1+2, 1+1+1, 2+1, 3
dp[4] = 7
// 1+3,
1+1+2, 2+2,
1+2+1, 1+1+1+1, 2+1, 3+1
-> dp[4]는 1에 3을 더한것, 2에 2를 더한것, 3에 1을 더한 것. 1부터 3까지로만 더할 수 있으므로 dp[i]=dp[i-1]+dp[i-2]+dp[i-3] 이다. (단, i>3)