[백준 15988] 1,2,3 더하기 3

알고리즘 분류 : 다이나믹 프로그래밍

문제 : 1,2,3 더하기 3

위 문제는 1, 2, 3 더하기  문제에서 n의 범위가 더 커졌고 모듈러 연산을 하면 되는 문제이다.

따라서 이 문제는 여기에서 세운 점화식에다가 모듈러 연산만 추가 하면 된다.

#include<cstdio>
 
long long dp[1000001] = {0, 1, 2, 4 };
 
const long long mod = 1000000009;
 
long long DP(int n)
{
    if (n <= 0)return 0;
    if (dp[n])return dp[n];
    for (int i = 4; i <= 1000000; i++)
    {
        dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % mod;
    }
    return dp[n];
}
 
int main()
{
    long long T;
    long long n;
    scanf("%lld", &T);
    for (; T--;)
    {
        scanf("%lld", &n);
        printf("%lld\n", DP(n));
    }
    return 0;
}