[BOJ 2302] 극장 좌석

#include <bits/stdc++.h>
using namespace std;
int N, M, a[41];
int dp[41];
int ans = 1;
int main() {
    cin >> N;
    cin >> M;
    for(int i = 0; i < M; i++) {
        cin >> a[i];
    }
    dp[0] = 1;
    dp[1] = 1;
    dp[2] = 2;
    int cnt = 1;
    int s = 0;
    for(int i = 3; i <= 40; i++) dp[i] = (dp[i-1] + dp[i-2]);
    for(int i = 0; i < M; i++) {
        int e = a[i];
        ans *= dp[e - s - 1];
        s = e;
    }
    ans *= dp[N - s];
    cout << ans;
}

$D[i]$ 를 vip석 없이 1~i 를 배치하는 경우의 수라고 점화식을 정의하자. 그러면 두 가지 케이스로 나눠야하는데,

1. $i$번째 좌석에 $i$번 사람이 앉을 때 => 이 때는 그냥 $i-1$ 번째만 잘 앉으면 되니까 $D[i-1]$

2. $i$ 번째 좌석에 $i-1$번 사람이 앉을 때 => 이 땐 $D[i-1]$ 이랑 $D[i]$ 가 고정이다. (둘이 바꿨으니까) 그러면 $D[i-2]$ 만 잘 앉으면 된다.

즉 $D[i] = D[i-1] + D[i-2]$ 인데, vip 석이 문제다. 근데 vip 석이 생길 때 마다 연속으로 앉는 자리의 개수가 초기화 되니까 , vip 석 사이의 거리를 계산해주면 된다.