백준 2302 극장좌석

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

쉬운 DP 문제입니다. x개의 연속된 좌석을 채우는 가지수는 항상 동일하므로 1~40개의 연속된 좌석을 memo 배열에 모두 구해놓고 memo[고정좌석 사이의 좌석수]를 모두 곱해주면 됩니다.

memoization식은 memo[x]=memo[x-1]+memo[x-2] 입니다. 가장 오른쪽에 앉아있는 사람은 현재 자리를 유지하는 경우는 memo[x-1]과 동일하고, 앞으로 한 칸 땡기는 경우 한칸 앞에 있던 사람이 뒤로 가지 않으면 모든 사람이 앉을 수 없기 때문에 둘이 자리를 바꾸는 경우만이 가능하여 memo[x-2]와 동일하기 때문입니다.

#include<bits/stdc++.h>
using namespace std;
const int SZ=45;
int memo[SZ];
int vip[SZ];
int main(void){
	ios::sync_with_stdio(false); cin.tie(NULL);
	memo[0]=1; memo[1]=1;
	for(int i=2;i<SZ;i++){
		memo[i]=memo[i-1]+memo[i-2];
	}
	int n,m; cin>>n>>m;
	for(int i=1;i<=m;i++) cin>>vip[i];
	sort(vip+1,vip+m+1);
	vip[m+1]=n+1;
	int ans=1;
	for(int i=0;i<=m;i++){
		ans*=memo[vip[i+1]-vip[i]-1];
	}
	cout<<ans;
	return 0;
}