[C/C++ 백준 2302번] 극장좌석 (Silver 2)

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

2302번: 극장 좌석

VIP석을 기준으로 완전히 나뉘므로, 나머지 것들의 경우의 수를 모두 구해 곱해주면 된다. 그리고 각각의 경우의 수들은 모두 피보나치 수열의 항들이다. (i번째 사람이 자릴 바꾸는 경우와 안바꾸는 경우)

 

#include <cstdio>
int main(void){
	int N, M, cnt=1, t1=0, t2=0;
	scanf("%d %d",&N, &M);
	int dp[41]={1,1,2};
	for(int i=3; i<41; i++){
		dp[i] = dp[i-1] + dp[i-2];
	}
	for(int j=0; j<M; j++){
		scanf("%d",&t2);
		cnt *= dp[t2-t1-1];
		t1=t2;
	}
	cnt =cnt*dp[N-t2];
	printf("%d",cnt);
}