1563.cpp

// 1563. 개근상
// 2021.05.15
// 다이나믹 프로그래밍
#include<iostream>

using namespace std;

int d[1001][2][3]; // d[i][j][k] : 길이 i, 지각횟수 j, 연속 결석 k

const int kDiv = 1'000'000;

int main()
{
    int n;
    cin >> n;

    d[1][0][0] = 1;
    d[1][1][0] = 1;
    d[1][0][1] = 1;

    for (int i = 2; i <= n; ++i)
    {
        d[i][0][0] = (d[i - 1][0][0] + d[i - 1][0][1] + d[i - 1][0][2]) % kDiv;
        d[i][0][1] = d[i - 1][0][0];
        d[i][0][2] = d[i - 1][0][1];

        d[i][1][0] = (d[i - 1][0][0] + d[i - 1][0][1] + d[i - 1][0][2] + d[i - 1][1][0] + d[i - 1][1][1] + d[i - 1][1][2]) % kDiv;
        d[i][1][1] = d[i - 1][1][0];
        d[i][1][2] = d[i - 1][1][1];
    }

    int ans = (d[n][0][0] + d[n][0][1] + d[n][0][2] + d[n][1][0] + d[n][1][1] + d[n][1][2]) % kDiv;
    cout << ans << endl;
    return 0;
}