[백준] 극장 좌석

참고 : www.acmicpc.net/problem/2302

2302번: 극장 좌석

- dp 문제

- dp[i] : dp[i-1] + dp[i-2] (ex. 1234 -> dp[3] 123 + 4 : 하나만 바꿈, dp[2] 12 + 34 : 둘 다 바꿈 )

- 나머지는 중복되므로 dp[i] = dp[i-1] + dp[i-2]가 성립.

- 경우의 수에 따라 vip 좌석 전 후 경우의 수 : a*b (ex a : 2가지 b: 2가지 = a*b)

 

import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] dp = new int[N+1];
        int answer = 1;
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= N; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }

        int prevVip = 0;

        for (int i = 1; i <= M; i++) {
            int vip = sc.nextInt();
            answer *= dp[vip - prevVip - 1];
            prevVip = vip;
        }

        answer *= dp[N - prevVip];

        System.out.println(answer);
    }
}