문제

image.png

image.png

코드

#include<stdio.h>
long long  dp[1000001];
int main() {

    int n,t;
    scanf("%d",&t);

    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;


    for(int i = 4; i <= 1000001; i++) {
        dp[i] =( dp[i-1] + dp[i-2] + dp[i-3] ) % 1000000009;
    }


    while(t--) {
        scanf("%d",&n);
        printf("%lld\n",dp[n]);
    }

    return 0;
}