[백준 02302] 극장 좌석 [Python]

문제

어떤 극장의 좌석은 한 줄로 되어 있으며 왼쪽부터 차례대로 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)

---

풀이

VIP를 제외한 부분 수열에 대해 그대로 앉는 방법과, 이전 자리에 앉는 방법에 대해 모든 가짓수를 곱해주는 문제다.

우선 VIP 회원의 위치를 입력을 받자.

dp[i] : ? ~ i 좌석에 앉을 수 있는 최대 가짓수

문제에서는 VIP 가 아닌 회원은 자신의 위치와 왼쪽, 오른쪽을 앉을 수 있다고 했지만 점화식에서는 자신의 위치와 이전 위치(왼쪽)만을 고려하여 단순화 시킨다.

• i 번 회원이 i자리에 앉는 경우 dp[i - 1],
• i 번 회원이 i - 1자리에 앉는 경우 dp[i - 2]

따라서 dp[i] = dp[i - 1] + dp[i - 2]가 성립한다.

단, i와 i - 1, i -2 중에 VIP 가 존재하는 경우를 고려해야 한다.

VIP가 아닌 일반 회원이 앉는 좌석은 1 ~ 2에 대한 계산을 편하게 하기위해 dp를 전부 1로 초기화하자.

i 번 회원이 VIP가 아니고, i - 1번 좌석이 VIP 좌석이 아니라면, 위의 점화식이 성립한다.

만약 i - 2좌석이 VIP좌석인 경우 이미 이전 좌석dp[ i -1 ]을 계산할 때 not vip[i - 1]에 의해 dp[i - 1] = 1 이므로,  점화식을 그대로 적용할 수 있다.

만약 현재 좌석이 VIP좌석이라면, dp는 유지하고, 결과값에 이전 좌석의 모든 경우의 수 ( dp[i - 1] ) 를 곱해주자

탐색이 끝난 후 N, N - 1번째가 일반 좌석이라면 dp[N]은 2 이상이다. 한 번 더 곱해주자.

---

소스코드

보기

---

출처

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