#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 석 사이의 거리를 계산해주면 된다.
'PS > baekjoon' 카테고리의 다른 글
[BOJ 2504] 괄호의 값 (0) | 2023.09.17 |
---|---|
[BOJ 1463] 1로 만들기 2 (0) | 2023.07.18 |
[BOJ 11055] 가장 큰 증가하는 부분 수열 (1) | 2023.07.17 |
[BOJ 1431] 시리얼 번호 (0) | 2023.07.16 |
[BOJ 2295] 세 수의 합 (1) | 2023.07.03 |