문제

풀이

1. n이 최대 40까지니까 40번 좌석까지 경우의 수를 미리 구해둔다.
2. 경우의 수를 구하는 점화식은 dp[n]=dp[n-1]+dp[n-2]이다.
3. vip 좌석이 생기면 vip 좌석을 기준으로 구간이 나뉘게 된다. 나뉘어진 구간들의 경우의 수를 곱해주면 정답 도출

코드

import java.io.*;
public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

		int n=Integer.parseInt(br.readLine());
		int m=Integer.parseInt(br.readLine());
		int[] dp=new int[41];
		dp[0]=1;   // m이 0일 경우 dp[0]이 곱해지기 때문에 1로 초기화
		dp[1]=1;
		dp[2]=2;
		for(int i=3;i<n+1;i++)dp[i]=dp[i-1]+dp[i-2];
		int ans=1;
		int before=0;
		for(int i=0;i<m;i++){
			int a=Integer.parseInt(br.readLine());
			ans=ans*dp[a-before-1];
			before=a;
		}
		ans=ans*dp[n-before]; //마지막 구간도 곱해주기
		System.out.println(ans);
	}
}

#dp