[BOJ/Python] 백준 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)

풀이

import sys

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
vip = [int(sys.stdin.readline()) for _ in range(m)]

dp = [0] * (n + 1)
dp[0] = 1
if n >= 1:
    dp[1] = 1
if n >= 2:
    dp[2] = 2
# dp[3] = 3

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


answer = 1
if m > 0:
    pre = 0
    for j in range(m):
        answer *= dp[vip[j] - 1 - pre]
        pre = vip[j]
    answer *= dp[n - pre]
else:
    answer = dp[n]
print(answer)

 

n = 전체 좌석 수

m = 고정석의 개수

 

확률과 통계 문제같다..

n = 1일 때: 1

n = 2일 때: 2

n = 3일 때: 3

n = 4일 때: 5

n = 5일 때: 8

12345

21345

21435

21354

13245

13254

12435

12354

... -> 식: 앞선 두 행의 값을 더한다 n = (n - 1) + (n - 2)

 

1. 만약 vip가 존재하는 경우, 각각 떨어진 자리라고 가정하고, n = 1로 초기화해 해당 경우의 수를 곱해준다.
   (pre: j번째 vip의 번호)
2. 입력받은 vip의 리스트를 돌면서 각각 떨어진 자리의 경우의 수를 정답에 곱해준다.
3. 리스트를 다 돌고 나서, 마지막 vip에서부터 마지막 자리까지 경우의 수를 정답에 곱해준다.
4. vip가 없는 경우, 순수 dp값을 정답으로 출력한다.