BOJ) 극장 좌석

극장 좌석

2302번: 극장 좌석

1 ~ N 까지 극장에 좌석이 존재한다.

VIP 티켓을 가진 사람은 티켓에 적힌 번호에 딱 앉는다.

나머지 일반 티켓의 경우 좌우로 1씩 증감한 번호에 앉을 수 있다.

이 때, 좌석에 배치할 수 있는 좌석표의 경우의 수를 구하는 문제다.

 

문제 자체는 크게 어렵지 않았다.

N =1 일 때, 1가지 경우가 존재하고,

N =2 일 때, 2가지 경우 (1, 2) 와 (2,1)이 존재한다.

N =3 일 때, (1,2,3), (1,3,2), (2,1,3)이 존재한다.

같은 방법으로

N =4일 때, 5가지 경우

N =5일 때, 8가지 경우가 존재한다.

 

여기까지 보면, 점화식이 존재한다.

dp[n] = dp[n-1] + dp[n-2] 라는 식이 세워진다.

 

여기서 VIP 좌석을 골라내는 작업이 조금 어려웠다.

처음에는 Queue를 사용해서, dp를 채워나갈 때, VIP 좌석인 경우와 이전 좌석이 VIP 좌석이었던 경우 등으로 조건문을 걸어서 초기화해주려고 했다.

하지만, 조건의 경우가 많아지고 문제의 답도 제대로 낼 수 없었다.

 

마지막으로 시도한 것은 dp 자체를 만들어 두고, 각 일반 좌석들의 점화식에 해당하는 N을 구하는 것이다.

1 ~ N까지 담긴 점화식을 먼저 초기화해줬다.

다음, 고정된 자리인 VIP 티켓을 쭉 훑으면서, 해당 VIP 좌석 전까지 일반 좌석이 몇 좌석 있는지 값을 구했다. 구해진 값은 점화식에 들어갈 n이 되고, 해당 경우의 수를 곱해주었다.

마지막 VIP 좌석 이후에 일반 좌석이 존재할 수 있기 때문에, dp[n-마지막 VIP 티켓 좌석]을 곱해주어 답을 구했다.

 

 

코드

 

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

public class TheaterSeat_2302 {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine()), m = Integer.parseInt(br.readLine());
    int[] fixedSeat = new int[m];
    for(int i=0; i<m; i++) {
      fixedSeat[i] = Integer.parseInt(br.readLine());
    }

    br.close();
    solution(n, fixedSeat);
  }

  private static void solution(int n, int[] fixedSeat) {
    int[] dp = initDp(n);
    int answer =1;
    int prev =0;
    for(int seat : fixedSeat) {
      answer *= dp[seat-prev-1];
      prev = seat;
    }
    answer *= dp[n-prev];

    System.out.println(answer);
  }

  private static int[] initDp(int n) {
    int[] dp = new int[n+1];
    dp[0] =1;
    dp[1] =1;
    for(int i=2; i<=n; i++) {
      dp[i] = dp[i-1] +dp[i-2];
    }
    return dp;
  }
}