[백준] 극장 좌석 (자바)

백준 URL
https://www.acmicpc.net/problem/2302

문제 풀이

좌석은 한 줄로 되어 있고 왼쪽부터 차례로 1번 ~ N번까지 번호가 있습니다.

일반적으로 입장권에 5번이 쓰여 있다면 4번, 6번과 같이 옆자리에 앉을 수 있습니다.

하지만 VIP 회원들은 반드시 자기 좌석에만 앉아야 하다는 특징이 있습니다.

이 문제를 해결하기 위해서는 DP를 사용해야합니다.

VIP 경우를 차치하고 문제를 접근하면

N=1일 때 경우의 수는 1가지입니다.

N=2일 때 경우의 수는 2가지입니다.

N=3일 때 경우의 수는 3가지 입니다.

N=4일 때 경우의 수는 5가지 입니다.

위 경우의 수를 통해 dp[N] = dp[N-1] + dp[N-2]라는 점화식을 도출할 수 있습니다.

만약에 중간 중간 VIP석이 껴있는 경우를 추가로 생각해야 하는데 VIP석은 고정석이기 때문에 VIP 양 옆 경우의 수를 서로 곱하면 총 경우의 수를 찾을 수 있습니다.

따라서 총 경우의 수는 VIP를 기준으로의 경우의 수들 간의 곱셈입니다.

코드

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

import java.lang.*;

public class Main{

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 어떤 극장의 좌석은 한 줄로 되어 있으며
        // 왼쪽부터 차례대로 1번부터 N번까지 번호가
        // 공연을 보러 온 사람들은 자기의 입장권에 표시된 자석에 앉아야 함
        // 입장권 5번 -> 5번 좌석

        // 7번 입장권을 가진 사람은 7번 좌석은 물론 6번, 8번에 앉을 수 있음
        // 그러나 5번 좌석이나 9번 좌석에는 앉을 수 없다

        // vip 회원
        // 반드시 자기 좌석에만 앉아야 함
        // 옆 좌석으로 자리를 옮길 수 없다.
        // 오늘 공연은 입장권이 매진되어 1번 좌석부터 N번 좌석까지 모든 좌석이 다 팔림

        int num = Integer.parseInt(br.readLine());

        int fixNumLen = Integer.parseInt(br.readLine());

        int[] arr = new int[num+1];
        int[] dp = new int[num+1];

        for (int i = 1; i <= num; i++){
            arr[i] = i;
        }

        for (int i = 0 ; i < fixNumLen ; i++){
            int fixNum = Integer.parseInt(br.readLine());

            arr[fixNum] = 0;
        }

        dp[0] = 1;
        for (int i = 1; i <= num; i++){
            if (i <= 2){
                dp[i] = i;
                continue;
            }

            dp[i] = dp[i-2] + dp[i-1];
        }

        // 1 2 3 0 5 6
        // 2 1 3 0 5 6
        // 1 3 2 0 5 6
        // 1 2 3 0 0 0

        // dp[n] = dp[n-2] + dp[n-1]
        // dp[1] = 1;
        // dp[2] = 2;

        // 1 2 3 0 5 6 0 8 9
        int n = 0;
        int total = 1;
        for (int i = 1; i <= num; i++){
            if (arr[i] == 0){
                total *= dp[n];
                n = 0;
            }
            else {
                n++;
            }

            if (i == num){
                total *= dp[n];
            }

        }


        bw.write(total+"");

        bw.flush();
        br.close();
        bw.close();
    }


}