백준 2302번 : 극장 좌석 [자바]

 

 

 

🧫 문제 분석

✔️ 출처

극장 좌석 실버 1

📖 문제

 

피보나치 수열 문제

vip 영역일때는 이전 값을 이어받는다

 

현재 좌석을 기준으로 

현재 좌석을 고정한 경우의 수 + 현재 좌석이 왼쪽 좌석과 교환했을 때 경우의 수를 구하면 된다.

1 2 3 4 이고 현재 4라면

1 2 3 | 4 로 4를 고정하고 1 2 3까지 의 경우의 수 dp[3]

+

1 2 | 4 3  으로 3과 교환하고 1 2 까지의 경우의 수 dp[2] 를 더한다

 

즉 점화식은

if (isVip[i] || isVip[i-1]) : dp[i] = dp[i-1]
else                        : dp[i] = dp[i-1] + dp[i-2]

 

vip 좌석은 따로 기록해놓고

피보나치 수열을 연산할때

현재 좌석 혹은 이전 좌석이 vip 좌석이면 

dp[i] = dp[i-1] 로 이어받는다.

 

 

---

🔅 문제 풀이

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        boolean[] isVipSeat = new boolean[n + 1];
        int[] dp = new int[n + 1];

        int m = Integer.parseInt(br.readLine());
        for (int i = 0; i < m; i++) {
            int seatNum = Integer.parseInt(br.readLine());
            isVipSeat[seatNum] = true;
        }

        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            // 현재 자리가 VIP 고정석이거나 이전 자리가 고정석이면 이전 경우의 수를 이어받는다.
            if (isVipSeat[i] || isVipSeat[i-1]) {
                dp[i] = dp[i - 1];
            } else {
                // 현재 자리를 고정했을 경우의 수(i-1) + 현재 자리를 앞의 자리와 변경했을 때 경우의 수 (i-2)
                // 1 2 3 일때 3을 고정했을 때 dp[2]의 경우의 수
                // 1 3 2 로 3을 2와 교환했을 때 dp[1]의 경우의 수
                dp[i] = dp[i - 1] + dp[i - 2];
            }
        }

        System.out.print(dp[n]);

    }
}

 

🔅 문제 풀이 [VIP 구간]

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        boolean[] isVipSeat = new boolean[n + 1];
        int[] dp = new int[n + 1];

        int m = Integer.parseInt(br.readLine());
        for (int i = 0; i < m; i++) {
            int seatNum = Integer.parseInt(br.readLine());
            isVipSeat[seatNum] = true;
        }

        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        int sum = 1;
        int preVip = 0;

        for (int i = 1; i <= n; i++) {
            if (isVipSeat[i]) {
                sum *= dp[i - preVip - 1];
                preVip = i;
            }
        }
        sum *= dp[n - preVip];

        System.out.print(sum);

    }
}

 

❗ 오답노트 / 필요한 지식

1.  이런 걸 구할땐 vip 즉 고정석 등 조건이 없을때를 생각해서 먼저 구해보자