[C++] 백준(BOJ) - 2302 : 극장 좌석
인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.
문제
떤 극장의 좌석은 한 줄로 되어 있으며 왼쪽부터 차례대로 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)
알고리즘
- DP
풀이
- idx를 증가시켜가며 가지수 체크만 하면 되는 간단한 DP
- 경우의 수는 바꾸느냐 바꾸지 않느냐 두가지
- 두 경우의 수를 계속 진행해가며 int형 dp에 += 해나가기
코드
// BOJ - 2302 : 극장 좌석
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, tmp, cnt[41], dp[41];
int go(int pos)
{
if (pos >= n - 1) return 1;
if (cnt[pos]) return go(pos + 1);
int& res = dp[pos];
if (res != -1) return dp[pos];
res = 0;
if (!cnt[pos + 1]) res += (go(pos + 2) + go(pos + 1)); // 다음 좌석이 vip 좌석이 아니라면 앞의 두 좌석을 변경
else res += go(pos + 1); // 변경하지 않고 idx만 증가
return res;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> n >> m;
for (int i = 0; i < m; i++)
{
cin >> tmp;
cnt[tmp - 1] = 1; // 바꿀수 없는 vip 좌석 cnt 배열
}
memset(dp, -1, sizeof(dp));
cout << go(0) << '\n';
return 0;
}
평가
- 간단한 탑다운 방식의 DP문제
- vip 좌석을 미리 cnt 배열에 담아 두고 제한 조건을 만족시키도록 구현
