BaekJoon 2302번: 극장 좌석(C++)

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

2302번: 극장 좌석

풀이법

1) 전형적인 DP 문제로, 피보나치를 활용하여 푸는 문제이다.

[ ] [ ] [ ] [VIP] [ ] [ ] {VIP] [ ] [ ]

위와 같은 형식의 배열이 있다면, VIP 좌석은 움직일 수 없기에, [ ] 이 연속되는 수를 구하여, 경우의 수를 구해주면 되는 문제였다. 자유롭게 움직일 수 있는 칸의 개수를 확인한다음 미리 만들어진 dp배열의 값을 불러오는 것이 중요할 것이다.

dp 배열의 규칙은 dp[1] =1. dp[2]=2, dp[3]=3, dp[4]=5 .... 와 같은 피보나치의 형태를 띈다.

[ ] [ ] [ ] [VIP] [ ] [ ] {VIP] [ ] [ ]

위와 같은 배열의 경우 빈 공간의 길이를 활용한다면 dp[3]*dp[2]*dp[2]의 값이  총 경우의 수일 것이며 이는 12이다.

 

추가적으로 dp[0] 또한 꼭 지정해 주어야 했다. 

3 3

1 2 3

같은 경우 딱 1개만 나올 수 있는데, 스스로 만든 소스코드에서 모두가 VIP일 경우를 생각하지 못했기에, 한 번 틀렸었으니 풀때 이런 부분을 고려해야 한다는 점을 확실하게 알 수 있었다.

 

#include <string>
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#define INF 987654321
using namespace std;

int n, m;
int dp[41];
int vip[41];
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		int a;
		cin >> a;
		vip[a] = 1;
	}
	dp[0] = 1;
	dp[1] = 1;
	dp[2] = 2;
	for (int i = 3; i <= n; i++)
	{
		dp[i] = dp[i - 1] + dp[i - 2];
	}
	int cnt = 0;
	int ans = 1;
	for (int i = 1; i <= n;i++)
	{
		if (vip[i] != 1)
		{
			cnt++;
			if (i == n)
				ans = ans * dp[cnt];
		}
		else
		{
			ans = ans * dp[cnt];
			cnt = 0;
		}
	}
	cout << ans;
}