설명

4를 만들 수 있는 조합은 아래와 같습니다.

1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
1+3
3+1

 끝에 있는 숫자를 기준으로 오름차순으로 정렬하면 규칙을 찾을 수 있습니다.
끝자리가 1로 끝나는 경우에서 끝에 있는 1을 제외하고 자세히 살펴보겠습니다.

 1+1+1, 1+2+1, 2+1+1, 3인데 3을 제외하면 모두 숫자 3을 만들 수 있는 경우의 수 입니다.
  마찬가지로, 끝자리가 2로끝나는 경우에서 마지막 2를 제외한다면 (1+1,2)는 2를 제외하고 2를 만들 수 있는 경우 입니다.

1+1+1+1
1+2+1
2+1+1
3+1

1+1+2
2+2

1+3

점화식

dp[i] = dp[i-3] + dp[i-2] + dp[i-1] 

코드

#include<stdio.h>
int dp[10001];
int main() {
    int n,t,i;
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;

    for(i = 4; i<= 11; i++) {
        dp[i] = (dp[i-1]) + (dp[i-2]) + (dp[i-3]);
    }
    scanf("%d",&t);
    for(i = 0; i < t; i++) {
        scanf("%d",&n);
        printf("%d\n",dp[n]);
    }
    return 0;
}