[python] 2302, 극장 좌석 : 다이나믹 프로그래밍(DP)

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

 

예제

 

풀이

💡 풀이 포인트

( 1 ) 경우의 수를 구하는 방식

9개의 좌석 & 4, 7 VIP라고 하면 [1 ~ 3, 4, 5 ~ 6, 7, 8 ~ 9] 로 좌석을 분리해볼 수 있다. 

4, 7은 고정이기 때문에 그대로 두고,

1 ~ 3을 배치하는 경우의 수 * 5 ~ 6을 배치하는 경우의 수 * 8 ~ 9를 배치하는 경우의 수를 구하는 것이 해당 문제의 정답이 된다.

 

( 2 ) DP [ i ] = DP [ i - 1 ] + DP [ i - 2 ]

여기서 DP는 i개의 좌석이 있고 지정된 좌석이 없다고 할 때, 배치할 수 있는 경우의 수를 모아놓은 배열이다.

1개의 좌석일 때는 1개, 2개의 좌석일 때에는 2개, 3개의 좌석일 때에는 3개 ...

DP = [1, 2, 3, 5, 8, ..]

i = 1 : 1개	i = 2 : 2개	i = 3 : 3개	i = 4 : 5개	i = 5 : 8개
1	[1, 2], [2, 1]	[1, 2, 3], [2, 1, 3], [1, 3, 2]	[1, 2, 3, 4], [1, 2, 4, 3], [2, 1, 3, 4], [2, 1, 4, 3], [1, 3, 2, 4]	[1, 2, 3, 4, 5], [1, 2, 4, 3, 5], [1, 2, 3, 5, 4], [2, 1, 3, 4, 5], [2, 1, 4, 3, 5], [2, 1, 3, 5, 4] [1, 3, 2, 4, 5] [1, 3, 2, 5, 4]

 

따라서, 지정된 VIP석 이전까지 혹은 VIP석과 VIP석 사이에 몇개의 좌석이 있는지를 파악한 뒤, 위의 DP 배열을 통해 각각의 경우의 수를 구할 수 있다.

예를 들어 위처럼 [1 ~ 3, 4, 5 ~ 6, 7, 8 ~ 9]로 배열을 분리시켰다고 할 때,

>> 1 ~ 3은 세 개의 원소를 배치하는 것이므로 DP[3] = 3개

>> 5 ~ 6은 두 개의 원소를 배치하는 것이므로 DP[2] = 2개

>> 8 ~ 9도 두 개의 원소를 배치하는 것이므로 DP[2] = 2개 임을 확인 할 수 있다.

그리고 ( 1 )번의 공식을 적용해 DP[3] * DP[2] * DP[2] = 3 * 2 * 2 = 12 를 정답으로 얻을 수 있다.

 

( 3 ) DP[0] = 1

VIP 좌석이 인접하여 존재할 경우도 고려해주어야 한다. 만약, VIP 좌석이 4, 5 이렇게 존재한다면 이 두 VIP 좌석 사이의 좌석 수는 0이 되어 경우의 수에 곱해주었을 때 그동안의 모든 경우의 수가 초기화되는 문제가 발생한다.

따라서, DP[0] = 0이 아닌 DP[0] = 1로 설정해주어야 한다.

 

n = int(input())
m = int(input())
vip = [int(input()) for _ in range(m)]
dp = [1] * 45
dp[2] = 2

for i in range(3, n + 1):
  dp[i] = dp[i - 1] + dp[i - 2]

if n < 2:
  print(1)
else:
  ans = 1
  srt = 1
  for j in vip:
    ans *= dp[j - srt]
    srt = j + 1
  print(ans * dp[n + 1 - srt])

 

 

++ srt로 하나의 VIP 좌석을 넘어간 뒤, 새로운 시작점을 지정해준다. 예를 들어, 위의 예시에서 4의 VIP석을 지나간 이후에는 srt = 5로 지정해주어 시작점을 새롭게 설정해주는 것이다.