백준 알고리즘 2302번 문제 : 극장 좌석

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

2302번: 극장 좌석

오늘 포스팅할 문제는 극장 좌석 문제입니다 

 

문제는 백준 알고리즘 사이트를 확인해주세요~

 

문제 분석

어떤 극장의 좌석은 1줄로 되어있다. 왼쪽부터 차례대로 1번 부터 N번까지 번호가 매겨져 있다. (1<=N<=40)

입장권에 극장의 좌석 번호가 표시되어 있다. 사람들은 자기의 입장권에 표시된 좌석에 앉아야한다.

단

1. 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로는 자리를 옮길 수 있다.
2. VIP 좌석은 왼쪽 혹은 오른쪽 좌석과 자리를 바꾸기가 불가능하다.

VIP 회원들의 좌석 번호가 주어졌을때 사람들이 좌석에 앉는 서로 다른 방법의 가짓수는?

 

경우의 수를 출력하는 문제입니다.

 

해결 방법

문제를 한번에 풀려고 하면 상당히 복잡합니다!

 

N명의 사람들이 좌석을 서로 바꿔 앉는 모습을 머리속에서 떠올려보면.....  끔찍합니다.. - ㅇ -;;

 

작은 단위로 분리해서 문제에 접근하는 방법과 일일이 경우의 수를 따지는 방법이 있습니다.

 

저는 작은 단위로 분리해서 문제에 접근하는 방법인 Dynamic Programming을 사용했습니다.

 

DP를 세우기 위해 문제가 준 조건을 이용합니다!

 

1. 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로 자리를 옮길 수 있다.

2. VIP 좌석은 왼쪽 혹은 오른쪽 좌석과 자리를 바꾸기가 불가능하다.

 

아 그러면 한 사람이 할 수 있는 행동은 3가지 종류 밖에 없다는 것을 알 수 있군요. 

 

종류 1 - 자리를 바꾸지 않는 사람

종류 2 - 왼쪽 좌석과 자리를 옮기는 사람

종류 3 - 오른쪽 좌석과 자리를 옮기는 사람

 

그런데 왼편에 있는 사람이 오른쪽 사람과 자리를 바꾸게 되면 오른쪽 사람은 왼쪽 좌석과 자리를 바꾼게 됩니다.

 

기준이 애매하므로 기준을 1번 좌석에서 N번좌석으로 -> 방향으로 다시 생각해보아요!

 

종류 1 - 자리를 바꾸지 않는 사람 ( i, seats[i][0] )

종류 2 - 이미 자리를 바꾼 사람 ( i -1, seats[i][1] )

종류 3 - 자리를 바꿀 사람 ( i +1, seats[i][2] )

 

아래는 1부터 6번 좌석까지 있고 VIP 회원은 없는 경우를 가정한 경우입니다

이것을 재귀적으로 표현하면,

 

seats[i][0] = seats[i-1][0] + seats[i-1][1]

seats[i][1] = seats[i-1][2]

seats[i][2] = seats[i-1][0] + seats[i-1][1]

 

이렇게 됩니다!

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {
	vector<vector<long long>> seats;
	queue<int> vip;
	int n, m;
	
	cin >> n >> m;
	if (n < 1 || n>40 || m<0 || m>n) {
		return 0;
	}
	seats = vector<vector<long long>>(n + 1, vector<long long>(3, 0));
	for (int i = 1, temp; i <= m; i++) {
		cin >> temp;
		if (temp<1 || temp>n) {
			return 0;
		}
		vip.push(temp);
	}

	if (vip.empty() == false && vip.front() == 1) {
		seats[1][0] = 1;
		vip.pop();
	}
	else {
		seats[1][0] = 1;
		seats[1][2] = 1;
	}
	for (int i = 2; i <= n; i++) {
		if (vip.empty() == false && vip.front() == i) {
			seats[i][0] = seats[i - 1][0] + seats[i - 1][1];
			vip.pop();
		}
		else{
			seats[i][0] = seats[i - 1][0] + seats[i - 1][1];
			seats[i][1] = seats[i - 1][2];
			seats[i][2] = seats[i - 1][0] + seats[i - 1][1];
		}
	}
	cout << seats[n][0] + seats[n][1];
}

그대로 코드로 작성하면 답이 나옵니다~