15989.cpp

// 15989. 1, 2, 3 더하기 4
// 2021.04.26
// 다이나믹 프로그래밍
#include<iostream>

using namespace std;

int d[10001][4]; // d[i][j] : 합이 i인 수 중 j를 마지막으로 더한 경우의 수
int main()
{
    int t;
    cin >> t;

    // 초기값 구하기
    d[1][1] = 1; // 1
    d[1][2] = 0; // 없음
    d[1][3] = 0; // 없음

    d[2][1] = 1; // 1 + 1
    d[2][2] = 1; // 2
    d[2][3] = 0; // 없음

    d[3][1] = 1; // 1 + 1 + 1
    d[3][2] = 1; // 2 + 1 (또는 1 + 2 인데 중복)
    d[3][3] = 1; // 3

    // bottom - up으로 계산한다.
    // 1로 끝난 경우: 바로 앞에 더한 수는 1이 나올 수 있다.
    // 2로 끝난 경우: 바로 앞에 더한 수가 1, 2가 나올 수 있다
    // 3으로 끝난 경우: 바로 앞에 더한 수가 1, 2, 3이 나올 수 있다.
    for (int i = 4; i <= 10000; i++)
    {
        d[i][1] = d[i - 1][1];
        d[i][2] = d[i - 2][1] + d[i - 2][2];
        d[i][3] = d[i - 3][1] + d[i - 3][2] + d[i - 3][3];
    }

    int k;
    while (t-- > 0)
    {
        cin >> k;
        cout << d[k][1] + d[k][2] + d[k][3] << "\n";
    }
    return 0;
}