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

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

2302번: 극장 좌석

---

극장 좌석 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. N이 최대 40이므로, 경우의 수가 40!입니다.

따라서 백트래킹을 이용하면 시간 초과가 발생할 수 있습니다.

 

 

vip 좌석의 경우 고정석입니다. 따라서 vip 석을 제외하고, 경우의 수를 계산해야합니다.

아래의 경우, 가능한 좌석 배치는 1개입니다.

1

vip

아래의 경우 가능한 좌석 배치는 2개입니다.

1

2

vip

1 2 vip
2 1 vip

아래의 경우 가능한 좌석 배치는 3개입니다.

1

2

3

vip

1 2 3 vip
1 3 2 vip
2 1 3 vip

아래의 경우 가능한 좌석 배치는 5개입니다.

1

2

3

4

vip

1 2 3 4 vip
2 1 3 4 vip
1 3 2 4 vip
1 2 4 3 vip
2 1 4 3 vip

아래의 경우 가능한 좌석 배치는 8개입니다.

1

2

3

4

5

vip

1 2 3 4 5 vip
2 1 3 4 5 vip
1 3 2 4 5 vip
1 2 4 3 5 vip
2 1 4 3 5 vip

1 2 3 5 4 vip
1 3 2 5 4 vip
2 1 3 5 4 vip

좌석이 5개일 때, 가능한 좌석 배치는, 좌석이 4개일 때 가능한 좌석 배치에 5를 붙여주고, 좌석이 3개일 때 가능한 좌석 배치에 5, 4를 붙여 만들 수 있음을 알 수 있습니다.

 

따라서 다이나믹 프로그래밍의 테이블 d[i]는 아래와 같이 정의할 수 있습니다.

(단, d[i]는 좌석이 i개 일때, 가능한 좌석 배치의 수)

d[i] = d[i - 1] + d[i - 2]

따라서, vip석 사이사이의 좌석의 개수를 계산하고, 각 좌석의 개수에 따른 가능한 좌석 배치의 개수를 곱해주면 됩니다. 

 

테스트 케이스를 예로 들어보겠습니다.

1

2

3

4(VIP)

5

6

7(VIP)

8

9

• 첫번째 VIP와 첫번째 좌석 사이의 좌석의 개수는 3개
• 두번째 VIP와 두번째 VIP 사이의 좌석의 개수는 2개
• 두번째 VIP와 마지막 좌석 사이의 좌석의 개수는 2개입니다.

따라서 결과는 d[3] * d[2] * d[2] = 12입니다.

단, VIP석이 없는 경우 결과는 d[n]이며, 좌석이 모두 VIP석이어도 1이 출력되어야합니다.

 

아래는 전체 코드입니다.

#include <bits/stdc++.h>
using namespace std;

int d[41];  // d[i]는 좌석이 i개 일때, 가능한 좌석 배치의 수
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n, m; cin >> n >> m;
    int vip[40];
    for(int i = 0; i < m; i++) cin >> vip[i];   // vip 좌석 입력 받음

    d[0] = 1; d[1] = 1; d[2] = 2;   // 초기값
    for(int i = 3; i <= 40; i++)    // 테이블 채움
        d[i] = d[i - 1] + d[i - 2];

    if(m > 0){  // vip 좌석이 있는 경우
        vector<int> interval;

        interval.push_back(vip[0] - 1); // 첫번째 vip와 첫번째 좌석 사이 좌석의 개수
        interval.push_back(n - vip[m - 1]); // 마지막 vip와 마지막 좌석 사이 좌석의 개수

        for(int i = 0; i < m - 1; i++)
            interval.push_back(vip[i + 1] - vip[i] - 1);    // vip 사이 좌석의 개수

        int ans = 1;    
        for(auto i : interval) ans *= d[i]; // 각 좌석의 개수에 따른 가능한 좌석 배치의 개수를 곱해줌
        cout << ans;
    }else{  // vip 좌석이 없는 s경우
        cout << d[n];
    }
}

 

아래는 문제 풀이에 사용된 테스트케이스입니다.

9 0
-> 55

40 3
10
20
30
-> 14807375%

3 2
1 2
-> 1