[백준 2302 JAVA] 극장 좌석

 

피보나치 수열을 활용한 dp문제이다.

vip좌석은 고정된 좌석이므로 경우의수의 구분점이 된다

 

vip좌석 사이에 일반좌석 1개일때 : 1가지

2개일때 : 2가지

3개일때 : 3가지

4개일때 : 5가지

...

 

따라서 경우의수는 피보나치 수열과 동일하다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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[N + 1];//1 1 2 3
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= N; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        int answer = 1;
        int start = 0;

        for (int i = 0; i < M; i++) {
            int temp = Integer.parseInt(br.readLine());
            answer *= dp[temp - start - 1];
            start = temp;
        }
        answer *= dp[N - start];
        System.out.println(answer);
    }
}