[C++] 백준 2302번 극장 좌석

다이나믹 프로그래밍 문제입니다.

좌석은 한 줄로 되어있으며, 자신의 좌석에서 왼쪽, 오른쪽 좌석과 바꿔서 앉을 수 있습니다.
VIP좌석은 본인의 자리에만 앉을 수 있을 때 경우의 수를 구하는 문제입니다.

각 좌석의 크기마다 경우의 수를 구해보면
1 = 1
2 = 2
3 = 3
4 = 5
5 = 8
6 = 13
....
다음과 같습니다.
여기서 규칙을 찾아보면 피보나치 수열의 형태를 가지는 것을 알 수 있습니다.

그래서 VIP좌석이 되기 전까지 피보나치식으로 값을 쌓아주고 VIP가 되면
다시 그 일반좌석 위치부터 피보나치수열을 쌓아갑니다.
그리고 이를 모두 곱해주면 결과값이 나옵니다.

#include <iostream>
#include <cstring>
using namespace std;

int seat[50];
int DP[50];

int main(int argc, char *argv[])
{
	memset(seat, 0, sizeof(seat));
	memset(DP, 0, sizeof(DP));

	int n;
	int vipNum;
	int vip;
	int result = 1;

	cin >> n;
	cin >> vipNum;
	while (vipNum--) {
		cin >> vip;
		DP[vip] = -1;
	}

	DP[0] = -1;
	DP[n + 1] = -1;

	for (int i = 1; i <= n; ++i) {
		if (DP[i] == -1) {
			continue;
		}
		if (DP[i - 1] == -1) {
			DP[i] = 1;
			continue;
		}
		if(i > 1 && DP[i - 2] == -1){
			DP[i] = 2;
			continue;
		}
		DP[i] = DP[i - 1] + DP[i - 2];
	}

	for (int i = 1; i <= n + 1; ++i) {
		if (DP[i] == -1 && DP[i - 1] != -1) {
			result *= DP[i - 1];
		}
	}

	cout << result << endl;

	return 0;
}