#include <iostream>
using namespace std;
int d[10001][4];
int count = 0;
int main(void)
{
    int n;
    cin >> n;
    d[1][1] = 1;
    d[2][1] = 1;
    d[2][2] = 1;
    d[3][1] = 1;
    d[3][2] = 1;
    d[3][3] = 1;
    for (int i = 4; i <= 10000; i++)
    {
        d[i][1] = d[i - 1][1];
        d[i][2] = d[i - 2][2] + d[i - 2][1];
        d[i][3] = d[i - 3][3] + d[i - 3][1] + d[i - 3][2];
    }
    for (int i = 0; i < n; i++)
    {
        int m;
        cin >> m;
        cout << d[m][1] + d[m][2] + d[m][3] << "\n";
    }
    return 0;
}

문제 접근

1,2,3 더하기 문제와 다르게, 오름차순 정렬 된 것만 따진다. 따라서 다이내믹 배열을 1차원이 아닌 2차원으로 선언한다.

해결 방법

d[i][1] 은 i 의 합을 끝자리 1로 채웠다는 뜻이다. 따라서 i-1 원소에다가 +1 만 더해주면 된다.
따라서 식이 d[i][1] = d[i-1][1] 가 된다.
d[i][2] 은 i 원소를 끝자리 2로 채웠다는 식이다. 예를 들어 i가 4 라면은 1+1+2 또는 2+2 로 표현할 수 있다. 이는, i-2 원소에 끝자리 1에 +2 를 하거나 i-2 원소, 끝자리 2에 +2 를 한 것과 같다.
d[i][3] 은 i원소를 끝자리 3로 채웠다는 식이다. 이는 동일한 방법으로
d[i][3] = d[i-3][3] + d[i-3][1]+ d[i-3][2] 로 표현할 수 있다.