[B15990] - 1,2,3 더하기 5

https://www.acmicpc.net/problem/15990

마지막항이 무엇인지 고려하여 점화식을 세우면 된다.

#include<iostream>
using namespace std;
long long d[100001][4];
int main() {
    int T;
    cin >> T;
    d[1][1] = d[2][2] = d[3][3] = 1;
    d[3][1] = d[3][2] = 1;
    for (int i = 4; i <= 100000; ++i) {
        d[i][1] = (d[i - 1][2] + d[i - 1][3]) % 1000000009;
        d[i][2] = (d[i - 2][1] + d[i - 2][3]) % 1000000009;
        d[i][3] = (d[i - 3][1] + d[i - 3][2]) % 1000000009;
    }
    while (T--) {
        int n;
        cin >> n;
        cout << (d[n][1] + d[n][2] + d[n][3]) % 1000000009 << '\n';
    }
}