백준1563 개근상

문제

해결방안

dp[출석일수][지각수][연속빠진수]
로 일단 배열을 세팅한다.

1)ㅁㅁㅁㅁㅁ출석 (맨마지막날 출석한 경우)
dp[출석일수][지각수][0]
=dp[출석일수-1][지각수][0,1,2] #연속빠진수는 어차피 마지막날 출석이면 0으로 초기화

2)ㅁㅁㅁㅁㅁ지각 (맨마지막날 지각한 경우)
dp[출석일수][1][0]=dp[출석일수-1][0][0,1,2] #맨마지막날 지각하면 어차피 연속빠진수는 0으로 초기화 됨

3)ㅁㅁㅁㅁㅁ연속빠진수 (맨마지막날 결석한 경우)
dp[출석일수][0][2]=dp[출석일수-1][0][1]
dp[출석일수][0][1]=dp[출석일수-1][0][0]
dp[출석일수][1][2]=dp[출석일수-1][1][1]
dp[출석일수][1][1]=dp[출석일수-1][1][1]

코드

#include <iostream>
int mod = 1000000;
using namespace std;

int main()
{
    int k;
    int ***dp;
    int x,y,z;
    int i,j,m;
    int result = 0;;
    cin >> x;
    dp = new int **[x+1];

    for (i = 0; i < x+1; i++) {
        dp[i] = new int *[2];
        for (j = 0; j < 2; j++) {
            dp[i][j] = new int[3];
        }
    }

    for (i = 0; i < x + 1; i++) {
        for (j = 0; j < 2; j++) {
            for (m = 0; m < 3; m++) {
                dp[i][j][m] = 0;
            }
        }
    }


    dp[0][0][0] = 1;
    dp[1][0][0] = 1;
    dp[1][0][1] = 1;
    dp[1][1][0] = 1;

    for (i = 2; i < x + 1; i++) {
        for (j = 0; j < 2; j++) {
            for (k = 0; k < 3; k++) {
                dp[i][j][0] += dp[i - 1][j][k];
                dp[i][j][0] %= mod;
                if (k < 2) {
                    dp[i][j][k + 1] += dp[i - 1][j][k];
                    dp[i][j][k + 1] %= mod;
                }
                if (j == 0) {
                    dp[i][1][0] += dp[i - 1][0][k];
                    dp[i][1][0] %= mod;
                }
            }
        }
    }
    for (j = 0; j < 2; j++) {
        for (m = 0; m < 3; m++) {
            result += dp[x][j][m];
        }
    }

    cout << result%mod;

    return 0;
}