[BOJ]9095 - 1,2,3 더하기 (C++)

문제

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

코드

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int dp[10001]; 

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

    int tc, n; 
    dp[1]= 1; dp[2]=2; dp[3]=4;
    cin >> tc; 
    for(int i=0; i<tc; i++){
        cin >> n; 
        for (int i=4; i<n+1; i++){
            dp[i] = dp[i-1]+ dp[i-2]+dp[i-3];
        }
        cout << dp[n] << "\n";
    }
}

풀이

다이나믹 프로그래밍을 하는 문제
1,2,3으로 만들어진 숫자를 생각하는 문제이기 때문에 구해야 하는 숫자-1, -2, -3을 보면 해결할 수 있다.
예를 들어 9를 1,2,3의 합으로 나타내기 위해서는 9보다 1,2,3 작은 수에 각각 1,2,3을 더하면 되기 때문에 이전에 구했던 6,7,8의 계산 결과를 이용하면 된다.