백준 - 2302번 : 극장 좌석 (C++)

풀이 방법 : DP

VIP를 제외한 이들은 양 옆의 자리에 앉을 수 있다.
왼쪽자리에 앉는 경우를 0, 제자리에 앉는 경우 1, 오른쪽 자리에 앉는 경우 2로 둔다면

DP[i][1] = DP[i-1][0] + DP[i-1][1] //VIP라면 이 경우만 구해준다.
DP[i][2] = DP[i - 1][0] + DP[i - 1][1]
DP[i][0] = DP[i - 1][2] // 빈 자리가 생기면 안되니 교차해서 앉는 경우만 고려해주자

이런식으로 점화식을 세워 연산 후 마지막까지 누적된 값을 출력해주면 된다.

#include <iostream>

using namespace std;

int N, M;
int  DP[41][3] = {};
bool IsVIP[41] = {};
int Answer = 0;

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

	cin >> N >> M;
	for (int i = 0; i < M; ++i)
	{
		int Num;
		cin >> Num;
		IsVIP[Num] = true;
	}

	if (N == 1)
	{
		cout << 1;
		return 0;
	}

	DP[1][1] = 1;
	
	if(!IsVIP[1])
		DP[1][2] = 1;

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

		if(!IsVIP[i])
		{
			DP[i][2] = DP[i - 1][0] + DP[i - 1][1];
			DP[i][0] = DP[i - 1][2];
		}
	}

	cout << DP[N][0] + DP[N][1];
}