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

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 < 231-1)

 

 

 

 

 

풀이)

 

#include <iostream>
#include <vector>
 
using namespace std;
 
int n, m;
vector<int> vec;
// 각 좌석에 대해 선택이 3가지이므로.
// dp는 2차원배열로 초기화된다.
int dp[41][4];
 
int recur(int cur, int idx)
{
    int ret = 0;
    
    // cur == n에 도달했다면 성공했으므로 return 1
    if (cur == n)
    {
        return 1;
    }
 
    // 고정석이라면 바로 다음걸로 넘어간다.
    if (vec[cur]) 
    {
        ret += recur(cur + 1, 1);
    }
    else
    {   // 범위를 넘어갈 수도 잇으므로 cur의 범위를 조절해준다.
        if (cur > 0 && !vec[cur - 1])
        {    
            vec[cur - 1] = 1;
            ret += recur(cur + 1, 0);
            vec[cur - 1] = 0;
        }
 
        if (!vec[cur])
        {
            vec[cur] = 1;
            ret += recur(cur + 1, 1);
            vec[cur] = 0;
        }
 
        if (cur < n && !vec[cur + 1])
        {
            vec[cur + 1] = 1;
            ret += recur(cur + 1, 2);
            vec[cur + 1] = 0;
        }
    }
 
    // 이미 계산한 값이라면 바로 return해준다.
    if (dp[cur][idx] != -1)
    {
        return dp[cur][idx];
    }
    
    dp[cur][idx] = ret;
 
    return dp[cur][idx];
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> n >> m;
    fill(dp[0], dp[0] + 41 * 4, -1);
    vec.resize(n + 1, 0);
 
    // 0번째 좌석은 없으므로 미리 막아놓는다.
    vec[0] = 1;
 
    // 고정석 먼저 앉힘.
    int temp;
    for (int i = 0; i < m; i++)
    {
        cin >> temp;
        vec[temp] = 1;
    }
 
    cout << recur(1, 0);
 
    return 0;
}
 

 

 

---

출처 : https://www.acmicpc.net/problem/2302 

2302번: 극장 좌석