[백준 2302] 극장 좌석 (C++)

https://www.acmicpc.net/problem/2302

2302번: 극장 좌석

문제

---

 어떤 극장의 좌석은 한 줄로 되어 있으며 왼쪽부터 차례대로 1번부터 N번까지 번호가 매겨져 있다. 공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다. 예를 들어서, 입장권에 5번이 쓰여 있으면 5번 좌석에 앉아야 한다. 단, 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로는 자리를 옮길 수 있다. 예를 들어서, 7번 입장권을 가진 사람은 7번 좌석은 물론이고, 6번 좌석이나 8번 좌석에도 앉을 수 있다. 그러나 5번 좌석이나 9번 좌석에는 앉을 수 없다.

그런데 이 극장에는 “VIP 회원”들이 있다. 이 사람들은 반드시 자기 좌석에만 앉아야 하며 옆 좌석으로 자리를 옮길 수 없다.

오늘 공연은 입장권이 매진되어 1번 좌석부터 N번 좌석까지 모든 좌석이 다 팔렸다. VIP 회원들의 좌석 번호들이 주어졌을 때, 사람들이 좌석에 앉는 서로 다른 방법의 가짓수를 구하는 프로그램을 작성하시오.

예를 들어서, 그림과 같이 좌석이 9개이고, 4번 좌석과 7번 좌석이 VIP석인 경우에 <123456789>는 물론 가능한 배치이다. 또한 <213465789> 와 <132465798> 도 가능한 배치이다. 그러나 <312456789> 와 <123546789> 는 허용되지 않는 배치 방법이다.

 

입력

---

첫째 줄에는 좌석의 개수 N이 입력된다. N은 1 이상 40 이하이다. 둘째 줄에는 고정석의 개수 M이 입력된다. M은 0 이상 N 이하이다. 다음 M 개의 줄에는 고정석의 번호가 작은 수부터 큰 수의 순서로 한 줄에 하나씩 입력된다.

 

출력

---

주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 2³¹-1)

 

문제 풀이

---

dp 문제.

1번부터 N번 좌석까지 반복문을 돌리며 가능한 가짓수를 구한다.

i번째 좌석이 고정석이라면 i-1번째 좌석까지의 가능한 가짓수와 같다. 이는 dp[i] = dp[i-1]로 표현된다.

i번째 좌석이 고정석이 아닌데 왼쪽 자리가 고정석이라면 i-1번째 좌석까지의 가능한 가짓수와 같다. (i번째 좌석까지만 고려하므로 오른쪽으로 자리를 옮기는 것은 고려하지 않는다.) 이는 dp[i] = dp[i-1]로 표현된다.

i번째 좌석이 고정석이 아니고, i-1번째 자리도 고정석이 아니라면 자리를 이동하지 않고 그대로 앉는 방법과, i-1번째 좌석과 바꾸는 방법이 있다. 첫번째는 dp[i-1]과 같고, 두번째는 i - 2번째까지의 좌석의 경우의 수에 i-1번째 좌석과 i번째 좌석을 서로 바꾸어 앉는 경우의 수 1을 곱한 dp[i-2]와 같으므로 두 경우의 합인 dp[i] = dp[i-1] + dp[i-2]와 같다.

 

아래는 코드.

#include <iostream>
using namespace std;

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

	int N, M, num;
	cin >> N;
	cin >> M;
	bool* isVIP = new bool[N+1];
	int* dp = new int[N+1];
	int current = 0;
	for (int i = 0; i < N+1; i++)
	{
		isVIP[i] = false;
	}
	for (int i = 0; i < M; i++)
	{
		cin >> num;
		isVIP[num] = true;
	}
	if (isVIP[1] == false)
	{
		current = 1;
	}
	else
	{
		current = 0;
	}
	dp[0] = 1;
	dp[1] = 1;
	for (int i = 2; i < N+1; i++)
	{
		if (isVIP[i] == false)
		{
			current++;
			if (current == 1)
			{
				dp[i] = dp[i - 1];
			}
			else
			{
				dp[i] = dp[i - 1] + dp[i - 2];
			}
		}
		else
		{
			current = 0;
			dp[i] = dp[i - 1];
		}
	}
	cout << dp[N] << "\n";
	return 0;
}