BOJ 15988번 1, 2, 3 더하기 3

BOJ : https://www.acmicpc.net/problem/15988

github : https://github.com/junho0956/Algorithm/blob/master/15988/15988/%EC%86%8C%EC%8A%A4.cpp

 

9095번 문제에서 dp의 범위를 늘려준 문제입니다.

이외는 동일합니다.

 

#include <iostream>
using namespace std;
#define MOD 1000000009
typedef long long ll;
 
ll dp[1000002];
 
ll dfs(int num) {
    if (num < 0) return 0;
    if (num == 0) return 1;
 
    ll& res = dp[num];
    if (res) return res;
 
    for (int i = 1; i <= 3; i++)
        res += dfs(num - i) % MOD;
 
    return res;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        cout << dfs(n) % MOD << "\n";
    }
    return 0;
}