[백준] 2302 극장 좌석(C++)

링크: https://www.acmicpc.net/problem/2302

2302번: 극장 좌석

문제

어떤 극장의 좌석은 한 줄로 되어 있으며 왼쪽부터 차례대로 1번부터 N번까지 번호가 매겨져 있다. 공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다. 예를 들어서, 입장권에 5번이 쓰여 있으면 5번 좌석에 앉아야 한다. 단, 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로는 자리를 옮길 수 있다. 예를 들어서, 7번 입장권을 가진 사람은 7번 좌석은 물론이고, 6번 좌석이나 8번 좌석에도 앉을 수 있다. 그러나 5번 좌석이나 9번 좌석에는 앉을 수 없다.

그런데 이 극장에는 “VIP 회원”들이 있다. 이 사람들은 반드시 자기 좌석에만 앉아야 하며 옆 좌석으로 자리를 옮길 수 없다.

오늘 공연은 입장권이 매진되어 1번 좌석부터 N번 좌석까지 모든 좌석이 다 팔렸다. VIP 회원들의 좌석 번호들이 주어졌을 때, 사람들이 좌석에 앉는 서로 다른 방법의 가짓수를 구하는 프로그램을 작성하시오.

 

예를 들어서, 그림과 같이 좌석이 9개이고, 4번 좌석과 7번 좌석이 VIP석인 경우에 <123456789>는 물론 가능한 배치이다. 또한 <213465789> 와 <132465798> 도 가능한 배치이다. 그러나 <312456789> 와 <123546789> 는 허용되지 않는 배치 방법이다.

 

입력

첫째 줄에는 좌석의 개수 N이 입력된다. N은 1 이상 40 이하이다. 둘째 줄에는 고정석의 개수 M이 입력된다. M은 0 이상 N 이하이다. 다음 M 개의 줄에는 고정석의 번호가 작은 수부터 큰 수의 순서로 한 줄에 하나씩 입력된다.

출력

주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 2^31-1)

---

풀이

VIP 좌석에 앉은 사람들 사이에 일반 좌석들이 몇 개 연속되어 있는지를 파악하고,

그 때 앉을 수 있는 경우의 수를 구하면 되는 문제이다.

일반 좌석들이 몇 개 연속되어 있는지는 입력값을 통해 쉽게 구할 수 있고, 경우의 수는 DP를 통해 구할 수 있다.

먼저 base case로 자리가 1개일 때의 경우의 수는 1개, 자리가 2개일 때의 경우의 수는 2개이다.

이후 자리가 3개일 때는 '3으로 끝나는 경우'와 '2로 끝나는 경우'를 구분하여 생각할 수 있다.

'3으로 끝나는 경우'는 자리가 2개일 때의 경우에 3을 더해주면 되고

'2로 끝나는 경우'는 자리가 1개일 때의 경우에 3, 2를 더해주면 된다.

따라서 자리가 3개일 때의 경우는 자리가 2개일 때의 경우 + 자리가 1개일 때의 경우로 구할 수 있다.

즉 점화식은 dp[n] = dp[n-1]+dp[n-2]이다.

 

자리가 4개일 때도 마찬가지이다.

자리가 4개인 경우는 '4로 끝나는 경우'와 '3으로 끝나는 경우'로 구분할 수 있고

'4로 끝나는 경우'는 자리가 3개인 경우와 동일하고

'3으로 끝나는 경우'는 자리가 2개인 경우와 동일하다.

따라서 자리가 4개인 경우 dp[4] = dp[3]+dp[2] = 3+2 = 5이다.

 

위와 같이 연속된 일반 좌석들의 경우의 수를 모두 구했다면 이들을 곱해주면 된다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, m;
vector<int> vipSeats;
int dp[41];

int main(){
    cin >> n;
    cin >> m;

    for (int i = 0; i < m; i++){
        int a;
        cin >> a;
        vipSeats.push_back(a);
    }

    // 미리 DP 테이블을 작성해둠
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; i++){
        dp[i] = dp[i-1]+dp[i-2];
    }

    // vip 좌석이 하나도 없는 경우
    if (m == 0){
        cout << dp[n];
        return 0;
    }
    // vip 자리에 따라 연속된 일반 좌석의 수를 계산
    int answer = 1;

    int left = 0;
    int right = vipSeats[0];
    answer *= max(1, dp[right-left-1]);

    for (int i = 1; i < m; i++){
        left = vipSeats[i-1];
        right = vipSeats[i];
        answer *= max(1, dp[right-left-1]);
    }

    left = vipSeats[m-1];
    right = n;
    answer *= max(1, dp[right-left]);

    cout << answer;
    return 0;
}