1563 개근상

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

d[i][j][k] = i일까지 지각 j번, 최근 연속 결석 k번한 출결정보의 수

#include <cstdio>
#define MOD 1000000
 
int n,d[1001][2][3],ans;
 
int main()
{
    d[0][0][0]=1;
    for(int i=1;i<1001;i++)
    {
        d[i][0][0]=d[i-1][0][0]%MOD+d[i-1][0][1]%MOD+d[i-1][0][2]%MOD;
        d[i][0][1]=d[i-1][0][0]%MOD;
        d[i][0][2]=d[i-1][0][1]%MOD;
        d[i][1][0]=d[i-1][0][0]%MOD+d[i-1][0][1]%MOD+d[i-1][0][2]%MOD+d[i-1][1][0]%MOD+d[i-1][1][1]%MOD+d[i-1][1][2]%MOD;
        d[i][1][1]=d[i-1][1][0]%MOD;
        d[i][1][2]=d[i-1][1][1]%MOD;
        
    }
    scanf("%d",&n);
    for(int i=0;i<2;i++) for(int j=0;j<3;j++)
        ans+=d[n][i][j],ans%=MOD;
    printf("%d\n",ans);
    return 0;
}