BOJ 2302 극장좌석

문제설명

접근방식

우선 DP방식을 이용해서 접근할 수 있다는 것은 알기 쉬운데 그렇다고 해서 단순하게 그래도 현재 인덱스 위치까지의 가능한 경우의 수로 DP를 설정해서 풀 수는 없다. VIP의 존재가 있기 때문에 불연속성이 발생하게 되고 이를 고려해서 처리를 해줄 필요가 있는데 일단 VIP의 존재를 배제하고 접근을 해보도록 하자.

서로 바꿀 수는 있지만 연속한 자리끼리만 바꿀 수 있는 경우의 수를 찾아가면서 그 안의 규칙성을 찾아본다.

(1)
1가지

(1, 2)
(2, 1)
2가지

(1, 2, 3)
(2, 1, 3)
(1, 3, 2)
3가지

(1, 2, 3, 4)
(2, 1, 3, 4)
(1, 3, 2, 4)
(1, 2, 4, 3)
(2, 1, 4, 3)
5가지

규칙은 i번째의 경우의 수는 i-1번째에서 찾은 조합에서 그대로 i의 수를 붙인 경우의 수와 그리고 그 중에서 끝에 수가 i-1이라서 i와 교환할 수 있는 경우의 수인데 이는 i-2번째에서 찾은 경우의 수와 동일하다. 동일한 방식으로 i-2에 찾은 경우의 수만큼 우선 i-1을 뒤에 붙이고 여기서 교환할 수 있는 경우의 수만큼을 추가한게 전체 i-1의 경우의 수이므로 i-1이 끝에 오는 경우의 수는 i-2의 값과 같아지는 것이다. 이런 방싯으로 접근하면 다음과 같은 DP 점화식을 세울 수 있다.

// DP 초기값 및 점화식
// DP[i] => i개의 연속된 좌석이 가질 수 있는 배치의 경우의 수
dp[0] = 1;
dp[1] = 1;
dp[i] = dp[i-1] + dp[i-2]

이렇게 연속한 좌석 수에 따른 경우의 수를 알았으므로 VIP석으로 인해서 구분된 좌석의 연속 수를 저장해서 해당하는 모든 DP 값을 곱해주면 구하고자 하는 모든 경우의 수를 구할 수 있다.

C++ 코드

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair <ll, ll>;

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  freopen("inp.txt", "r", stdin);

  // DP 선행처리
  int dp[41];
  dp[0] = 1;
  dp[1] = 1;
  for(int i=2; i<=40; i++)
    dp[i] = dp[i-1] + dp[i-2];

  vector <int> val;
  int N, M;
  cin >> N;
  cin >> M;

  // VIP로 구분된 좌석의 연속 수 저장하기
  if(M == 0)
    val.push_back(N);
  else{
    int idx = 1;
    while(M--){
      int vip;
      cin >> vip;
      val.push_back(vip-idx);
      idx = vip + 1;
    }
    val.push_back(N+1-idx);
  }

  // 좌석의 연속된 수 만큼 곱해서 모든 경우의 수 처리하기
  int ans = 1;
  for(int x : val)
    ans *= dp[x];
  cout << ans;
}