DP 문제 해결 - 백준 극장 좌석

문제

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

2302번: 극장 좌석

 

문제

- 어떤 극장의 좌석은 한 줄로 되어 있으며 

- 왼쪽부터 차례대로 1번부터 N번까지 번호가 매겨져 있다.

- 공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다.

- 예를 들어서, 입장권에 5번이 쓰여 있으면 5번 좌석에 앉아야 한다.

- 단, 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로는 자리를 옮길 수 있다.

- 예를 들어서, 7번 입장권을 가진 사람은 7번 좌석은 물론이고, 6번 좌석이나 8번 좌석에도 앉을 수 있다.

- 그러나 5번 좌석이나 9번 좌석에는 앉을 수 없다.

 

- 이 극장에는 “VIP 회원”들이 있다. 

- 이 사람들은 반드시 자기 좌석에만 앉아야 하며 옆 좌석으로 자리를 옮길 수 없다.

 

- 오늘 공연은 입장권이 매진되어 1번 좌석부터 N번 좌석까지 모든 좌석이 다 팔렸다.

- VIP 회원들의 좌석 번호들이 주어졌을 때, 사람들이 좌석에 앉는 서로 다른 방법의 가짓수를 구하는 프로그램을 작성하시오.

 

- 예를 들어서, 그림과 같이 좌석이 9개이고, 4번 좌석과 7번 좌석이 VIP석인 경우에 <123456789>는 물론 가능한 배치이다.

- <213465789>와 <132465798>도 가능한 배치이다.

- 그러나 <312456789>와 <123546789>는 허용되지 않는 배치 방법이다.

입력

- 첫째 줄에는 좌석의 개수 N이 입력된다. N은 1 이상 40이하이다. 

- 둘째 줄에는 고정석의 개수 M이 입력된다. M은 0 이상 N 이하이다.

- 다음 M개의 줄에는 고정석의 번호가 작은 수부터 큰 수의 순서로 한 줄에 하나씩 입력된다.

 

참고

https://steady-coding.tistory.com/178

 

import java.io.*;

public class Main {
	public static void main(String[] args) throws IOExcpetion {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        
        int[] dp = new int[41];
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        
        for (int i = 3; i <= N; i++) {
        	dp[i] = dp[i - 1] + dp[i - 2];
            }
            
            int ans = 1;
            
            // vip 좌석을 제외한 나머지 좌석의 경우의 수를 서로 곱함
            int beforeSeat = 0;
            for (int i = 0; i < M; i++) {
            		int temp = Integer.parseInt(br.readLine());
                    ans *= dp[temp - beforeSeat - 1];
                    beforeSeat = temp;
            }
            ans *= dp[N - beforeSeat]; // 마지막 vip 좌석 다음 좌석에서 끝 좌석까지의 경우의 수
            
            bw.write(ans + "\n");
            bw.flush();
            bw.close();
            br.close();
    }