문제
N개의 좌석이 일렬로 있고, 각 사람은 자기 좌석 또는 바로 인접한 좌석에만 앉을 수 있다. M개의 VIP 좌석은 반드시 해당 번호 좌석에 앉아야 할 때, 가능한 배치 수를 구하라.
입력
첫째 줄에 N (1 이상 40 이하), 둘째 줄에 M (0 이상 N 이하), 이후 M개의 VIP 좌석 번호가 주어진다.
출력
가능한 좌석 배치 수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
9 2 4 7 | 12 |
풀이
VIP 좌석을 경계로 나뉜 각 구간의 배치 수를 피보나치로 구하고 곱한다.
dp[i] = dp[i-1] + dp[i-2](피보나치)로 길이 i인 연속 구간의 배치 수를 전처리한다- VIP 좌석들을 순서대로 읽으며, 이전 VIP와 현재 VIP 사이 구간 길이를 계산한다
- 각 구간의 배치 수
dp[구간 길이]를 모두 곱한다 - 마지막 VIP 이후 남은 구간도 곱한다
핵심 아이디어: VIP 좌석이 고정점 역할을 하여 구간을 독립적으로 분리한다. 각 구간에서 인접 교환만 허용하는 배치 수는 피보나치 수열과 같다 (자기 자리에 앉거나 앞 사람과 교환).
코드
package day349;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class Day321BOJ2302극장좌석 {
public static void main(String[] args) throws Exception {
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;
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];
bw.write(ans + "\n");
bw.flush();
bw.close();
br.close();
}
}복잡도
- 시간: O(N) - 피보나치 전처리 + 구간별 곱셈
- 공간: O(N) - DP 배열