백준2302 - 극장 좌석

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

2302번: 극장 좌석

DP를 활용하여 푸는 문제다. 일반항은 a(n) = a(n - 1) + a(n - 2) (a[0] = 1, a[1] = 1, a[2] = 2)이다. 서로 2개씩 인접한 자리만 교환이 가능하다. 3개 이상 섞으면 두 칸 떨어진 곳으로 이동할 가능성이 있다.

 

ex.)

1칸(a) : a -> 1

2칸(a b) : a b, b a -> 2

3칸(a b c) : a b c, b a c, a c b -> 3

4칸(a b c d) : a b c d, b a c d, a c b d, a b d c, b a d c -> 5

5칸(a b c d e) : a b c d e, b a c d e, a c b d e, a b d c e, a b c e d, b a d c e, b a c e d, a c b e d -> 8

6칸(a b c d e f) : a b c d e f, b a c d e f, a c b d e f, a b d c e f, a b c e d f, a b c d f e, b a d c e f, b a c d f e,

a b d c f e, a c b d f e, a c b e d f, b a c e d f, b a d c f e -> 13

.

.

.

일반항 : a(n) = a(n - 1) + a(n - 2) (a[0] = 1, a[1] = 1, a[2] = 2)

 

#include <iostream>
#include <vector>
using namespace std;

vector<int> d;
vector<int> v;
int mat[41];
long long int ans = 1;

//교환 가능한 자리의 모든 경우의 수, 일반항 : a[n] = a[n - 2] + a[n - 1], a[0] = 0, a[1] = 1, a[2] = 2
void findDP() {
	for (int i = 0; i <= 40; i++) {
		if (i == 0) {
			d.push_back(0);
		}
		else if (i == 1) {
			d.push_back(1);
		}
		else if (i == 2) {
			d.push_back(2);
		}
		else {
			d.push_back(d[i - 1] + d[i - 2]);
		}
	}
}

int main() {
	int m, n;
	int cnt = 0;
	cin >> m;
	cin >> n;

	//고정석 표시
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		mat[x] = 1; //
	}

	//고정석을 기준으로 나눈 자리 교환한 자리
	for (int i = 1; i <= m; i++) {
		if (mat[i] == 1) { //고정석이면
			if (cnt == 0) { //고정석이 연속으로 붙어 있어서 교환 가능한 자리가 없으면
				continue; //무시
			}
			v.push_back(cnt); //고정석을 만나면 교환 가능한 자리를 벡터에 넣는다.
			cnt = 0; //교환 가능한 자리를 0으로 초기화
		}
		else { //교환 가능한 자리면
			cnt++; //교환 가능한 자리의 수를 증가
			if (i == m) { //마지막 자리가 교환 가능한 자리면
				v.push_back(cnt); //교환 가능한 자리의 갯수를 벡터에 넣는다.
			}
		}
	}

	findDP(); //DP실행

	//교환 가능한 자리의 수의 맞게 DP로 환산한 값을 모두 곱한다.
	for (int i = 0; i < v.size(); i++) {
		ans = ans * d[v[i]];
	}
	cout << ans;
}