백준 - 24464번 : 득수 밥 먹이기 (C++)

풀이 방법 : DP

문제에서 준 조건을 해석해보면 각각의 경우가 가능한 경우들은

1번 식당 : 전날(i - 1일)에 굶었거나 3번 혹은 4번 식당에 간 경우
2번 식당 : 전날에 굶었거나 4번 식당에 갔던 경우
3번 식당 : 전날에 굶었거나 1번 식당에 갔던 경우
4번 식당 : 전날에 굶었거나 1번 혹은 2번 식당에 갔던 경우.
굶을 수 있는 경우 : 전날에 굶지 않은 경우(전날에 1, 2, 3, 4에서 식사)한 경우

이 조건들에 따라 점화식을 세우고 각 결과값에 문제에서 주어진 수로 나눈 나머지를 누적해가면 된다.

#include <iostream>

using namespace std;

long long DP[200001][5] = {};
const long long Mod = 1000000007;

int main()
{
	cin.tie(nullptr);
	cout.tie(nullptr);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;

	DP[1][0] = 1;
	DP[1][1] = 1;
	DP[1][2] = 1;
	DP[1][3] = 1;
	DP[1][4] = 1;

	for (int i = 2; i <= N; ++i)
	{
		DP[i][0] = (DP[i - 1][1] + DP[i - 1][2] + DP[i - 1][3] + DP[i - 1][4]) % Mod;
		DP[i][1] = (DP[i - 1][0] + DP[i - 1][3] + DP[i - 1][4]);
		DP[i][2] = (DP[i - 1][0] + DP[i - 1][4]) % Mod;
		DP[i][3] = (DP[i - 1][0] + DP[i - 1][1]) % Mod;
		DP[i][4] = (DP[i - 1][0] + DP[i - 1][1] + DP[i - 1][2]) % Mod;
	}

	long long Answer = 0;

	for (int i = 0; i < 5; ++i)
	{
		Answer += DP[N][i] % Mod;
		Answer %= Mod;
	}

	cout << Answer;
}