14553번: The Way

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

시간복잡도는 $O(n)$

#include<cstdio>
#define mod int(1e9 + 9)
int n;
long long dp[1001][3] = { { 1,0,0 },{ 1,1,1 } };
int main() {
    scanf("%d", &n);
    for (int i = 2; i <= n; i++) {
        dp[i][0] = (dp[i - 1][0] * 2 + dp[i - 1][1] + dp[i - 1][2] - dp[i - 2][0] - dp[i - 2][1] + mod * 2) % mod;
        dp[i][1] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % mod;
        dp[i][2] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2] * 2 - dp[i - 2][1] - dp[i - 2][2] + mod * 2) % mod;
    }
    printf("%lld", dp[n][2]);
    return 0;
}