[알고리즘] C++ 백준 2302 극장좌석

 

백준 2302

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

2302번: 극장 좌석

풀이 전 나의 생각

N개의 극장 좌석과 M개의 VIP 좌석이 주어졌을 때 앉을 수 있는 서로 다른 방법의 가짓수를 구해야 한다.

조건

1. 일반석은 본인 자리에서 좌우로 움직일 수 있다.

2. VIP석은 움직일 수 없다.

 

이 조건을 만족하면서 나올 수 있는 경우들을 한 번 구해보자.

 

최대 자릿수가 1일 때

[1]

 

최대 자릿수가 2일 때

[1][2]

[2][1]

 

최대 자릿수가 3일 때

[1][2][3]

[2][1][3]

[1][3][2]

 

그럼 여기서 최대 자릿수가 3인 결과값에서 

[1][2][3]

[2][1][3] 

이 부분이 3의 자리가 고정이라고 가정하면 최대 자릿수가 2일 때 나올 수 있는 결과값과 겹치는 부분이 생긴다.

그럼 다음으로 나머지인

[1][3][2]

이 부분이 3의 자리가 고정이라고 가정하면 최대 자릿수가 1일 때 나올 수 있는 결과값과 겹치는 부분이 생긴다.

 

그럼 이를 점화식으로 표현하면 DP[N] = DP[N - 1] + DP[N - 2]가 나오는 것을 확인할 수 있다.

현재 점화식을 이용하여 N개의 자리에서 나올 수 있는 최대 가짓수를 구할 수 있는 상태다.

 

다시 문제로 돌아가서 점화식이란걸 생각안하고 최대값을 구하려고 했을 때 기본적으로 VIP가 있는 위치를 기준으로

자리의 최대 가짓수를 곱하면 되다는 것을 알 수 있다.

EX) 3까지 나올 수 있는 최대 가짓수 * 5부터 6까지 나올 수 있는 최대 가짓수 * 8부터 9까지 나올 수 있는 최대 가짓수

 

그러니 VIP 사이에 있는 자리 개수의 최대 가짓수를 구하여 곱해주고 최종 결과값을 반환해주면 된다.

 

주의해야할 점은 최종 결과값 변수에 최대 가짓수를 곱하여 넣어줘야 하기 때문에 변수 초기값과 DP[0]을 0이 아닌 1로 설정해줘야 한다.

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>



using namespace std;

int VIP[41];
int dp[41];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, m = 0;
	int start = 0;
	int ans = 1;
	cin >> n >> m;

	for (int i = 0; i < m; i++)
	{
		cin >> VIP[i];
	}

	dp[0] = 1;
	dp[1] = 1;
	dp[2] = 2;

	for (int i = 3; i <= n; i++)
	{
		dp[i] = dp[i - 1] + dp[i - 2];
	}

	for (int i = 0; i < m; i++)
	{
		int end = VIP[i];
		ans *= dp[end - start - 1];
		start = end;
	}

	ans *= dp[n - start];

	cout << ans;
}