[BOJ 2302] 극장 좌석 (Java, DP)

 

 

---

문제 링크 

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

2302번: 극장 좌석

---

문제 풀이 

- DP, 피보나치(fibonacci) 응용하여 풀면되는 문제였음 

- 시간 복잡도 O(N * M)

 

절차

(1) DP 배열에 좌석 개수별 경우의 수를 미리 구함

(2) 앉을 수 있는 좌석 범위를 각각 구한 후 곱셈 연산으로 결과값 구함

(이때 모든 좌석이 VIP인 경우 앉을 수 있는 경우의 수는 1)

 

*DP 초기항 구할 경우 
자리가 1개 일 때 1가지 경우의 수 
자리가 2개 일 때 2가지의 경우의 수 
자리가 3개 일 때 3가지의 경우의 수
자리가 4개 일 때 5가지의 경우의 수
...
(이때 자리가 0개 일 때 1가지의 경우의 수 처리 해줘야 함) 

---

제출 코드 

import java.util.*;
import java.io.*;

public class Main {
    
    static int N, M;

    static int[] DP;

    static List<Integer> range = new ArrayList<>();

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());

        DP = new int[N + 1];
        DP[0] = 1;
        DP[1] = 1;

        for(int i = 2; i <= N; i++) {
            DP[i] = DP[i - 1] + DP[i - 2];
        }

        int start = 0;
        for(int i = 1; i <= M; i++) {
            int end = Integer.parseInt(br.readLine());
            range.add(end - start - 1);
            start = end;
        }
        range.add(N - start);

        int ans = 1;
        for(int r : range) ans *= DP[r];

        System.out.println(ans);
    }

    public static void main(String[] args) throws Exception {
        input();
    }
    
}