백준 - 1563번 : 개근상 (C++)

풀이 방법 : DP

연속 결석일이 0일이 될 수 있는 경우는 이전날까지 연속 결석일이 며칠이 됐든 그 다음날 출석이든, 지각을 하는 경우다.

연속 결석일만 잘 처리하여 점화식을 구성할 수 있다면 다른 케이스들은 그렇게 어렵진 않다.

#include <iostream>

using namespace std;

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

	int DP[1001][3][2] = {};

	DP[1][0][0] = 1;
	DP[1][1][0] = 1;
	DP[1][0][1] = 1;

	for (int i = 2; i < N + 1; ++i)
	{
		DP[i][0][0] = DP[i - 1][0][0] % 1000000 
        			  + DP[i - 1][1][0] % 1000000
                      + DP[i - 1][2][0] % 1000000;
        
		DP[i][1][0] = DP[i - 1][0][0] % 1000000;
		DP[i][2][0] = DP[i - 1][1][0] % 1000000;

		DP[i][0][1] = DP[i - 1][0][0] % 1000000
                      + DP[i - 1][1][0] % 1000000 
                      + DP[i - 1][2][0] % 1000000 
                      + DP[i - 1][0][1] % 1000000 
                      + DP[i - 1][1][1] % 1000000 
                      + DP[i - 1][2][1] % 1000000;
            
		DP[i][1][1] = DP[i - 1][0][1] % 1000000;
		DP[i][2][1] = DP[i - 1][1][1] % 1000000;
	}

	int Answer = 0;

	for (int i = 0; i < 3; ++i)
	{
		for (int j = 0; j < 2; ++j)
		{
			Answer += DP[N][i][j];
			Answer %= 1000000;
		}
	}

	cout << Answer << endl;
	
}