[백준 14651] 걷다보니 신천역 삼 (large)

small 에서 범위만 늘려주고 mod연산만 추가하면 된다.

#include <iostream>
#define mod 1000000009
using namespace std;
 
 
int main(void) {
    int n;
    long long dp[33335][3];
    cin >> n;
 
    dp[1][0] = 0;
    dp[1][1] = 1;
    dp[1][2] = 1;
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j < 3; j++) {
            dp[i][j] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % mod;
        }
    }
 
    cout << dp[n][0] << endl;
}