백준 2302 극장 좌석 c++ (dp)

문제 출처 : 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 < 231-1)

알고리즘 분류

• 다이나믹 프로그래밍

풀이

dp 문제이지만, 입력 값이 작기 때문에 굳이 메모이제이션을 활용하지 않아도 풀 수 있을 것이다.

우선 vip 1 vip 인 경우 1가지,

vip 1 2 vip 인 경우 2가지,  1 2 / 2 1

vip x x x vip 인 경우 3가지이다. 1 2 3 / 2 1 3 / 1 3 2

vip x x x x vip 인 경우 

1 2 3 4

2 1 3 4

1 3 2 4

1 2 4 3

2 1 4 3

빨간색 부분은 일반석이 3자리인 경우, 파란색 부분은 일반석이 2자리인 경우이다.

즉 일반석이 i개일 때, 일반석이 i-1개인 경우+일반석이 i-2개인 경우를 더하면 일반석이 i개일 때의 경우를 구할 수 있다.

따라서 일반석의 개수를 i라고 할 때 dp[i]는 앉을 수 있는 경우의 수라고 하면 점화식은 다음과 같다.

dp[i] = dp[i-1]+dp[i-2]

위의 점화식을 이용해 일반석의 개수별로 앉을 수 있는 경우의 수를 구해놓고,

주어진 입력을 통해 vip좌석 혹은 배열의 마지막 부분 사이의 일반석의 개수들을 구해가며 곱해주면 모든 경우의 수를 구할 수 잇다. 

코드

#include <iostream>

using namespace std;

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

	int n,m;
	cin >> n >> m;
	int dp[41] = { 1,1,2 };
	for (int i = 3; i <= 40; i++) {
		dp[i] = dp[i - 1] + dp[i - 2];
	}
	int idx = 1;
	int answer = 1;
	
	for (int i = 0; i < m; i++) {
		int vip;
		cin >> vip;
		answer *= dp[vip - idx];
		idx = vip + 1;
	}
	answer *= dp[n+1 - idx];
	
	cout << answer;
	return 0;
}