문제 출처

1. 문제설명

• 좌석의 개수 N이 주어진다.
• 이 중 M개는 VIP 좌석이다.
• i번째 일반좌석은 i-1 또는 i+1 좌석에 앉을 수 있다.
• 그러나 VIP 좌석은 i번째 좌석에만 앉을 수 있다.
• N과 M이 주어질 때, 가능한 경우의 수를 구하라

2. 알고리즘 설계

• 1개, 2개의 좌석은 경우의 수가 각각 1개, 2개이다.
  • 좌석이 없는 경우(0개의 좌석)도 경우의 수로 취급되어 1개의 경우를 갖는다.
• 각 경우의 수는 피보나치 수열과 같은 점화식을 갖게 된다.
  • DP[i] = DP[i-1] + DP[i-2]
• 문제에서 VIP 좌석의 번호가 주어지는데, 0번 좌석과 N+1번 좌석을 VIP 좌석으로 지정한다.
• VIP 좌석은 변경될 수 없으므로, VIP 좌석의 경우를 배제하면 된다.
  • 누적합에서 사용하는 방식을 이용하면 된다.
  • DP[v[i] - v[i-1] - 1]
• 이 문제와 같은 경우는 동시성 확률이다.
  • 동시에 일어날 확률은 각 확률의 곱과 같다.
  • 머신러닝 수업에 나오는 내용이다!

3. 전체 코드

#include <bits/stdc++.h>
using namespace std;

const int SZ = 41;
int tmp, ans, n, m, DP[SZ];
vector<int> v;

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n >> m;

	v.push_back(0);
	while(m--) {
		cin >> tmp;
		v.push_back(tmp);
	}
	v.push_back(n+1);

	DP[0] = DP[1] = 1;
	DP[2] = 2;
	for(int i=3; i<=n; i++) DP[i] = DP[i-1] + DP[i-2];

	ans = 1;
	for(int i=1; i<v.size(); i++) ans *= DP[v[i] - v[i-1] - 1];

    cout << ans; 
	return 0;
}

4. 소감

• VIP 좌석이라는 특수한 경우로 인해 아이디어를 떠올리기 어려웠던 문제이다.
• 조건부 확률과, 누적합 스킬을 사용하여 풀이할 수 있었다.