baekjoon/DP
백준 2302번 : 극장 좌석 [자바]
Meluu_
2025. 5. 8. 09:51
🧫 문제 분석
✔️ 출처
📖 문제

피보나치 수열 문제
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);
}
}
❗ 오답노트 / 필요한 지식
- 이런 걸 구할땐 vip 즉 고정석 등 조건이 없을때를 생각해서 먼저 구해보자