[BOJ] 2302 극장 좌석 C++

개요

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

2302번: 극장 좌석

 

그냥저냥 풀만한 DP문제다.

 

풀이

VIP를 기준으로 집단을 나누었다.

각 집단들의 경우의 수(피보나치 수)를 곱하면 모든 경우의 수를 구할 수 있다.

 

코드

#include<iostream>
#include<algorithm>
using namespace std;
int main() {
	cin.tie(0)->sync_with_stdio(0);
	int dp[41] = { 0, 1, 2 };
	int N, M;
	int result = 1;
	cin >> N >> M;
	for (int i = 3; i < 41; i++)
		dp[i] = dp[i - 1] + dp[i - 2];

	int lastVip = 0;
	while (M--)
	{
		int vip;
		cin >> vip;
		if(vip - lastVip - 1 > 0)
			result *= dp[vip - lastVip - 1];
		lastVip = vip;
	}
	if(N != lastVip)
		result *= dp[N - lastVip];
	cout << result;
}