[백준/2302/파이썬] 극장 좌석

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

2302번: 극장 좌석

Problem

• 어떤 극장의 좌석은 한 줄로 되어 있으며 왼쪽부터 차례대로 1번부터 N번까지 번호가 매겨져 있다. 공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다. 
• 오늘 공연은 입장권이 매진되어 1번 좌석부터 N번 좌석까지 모든 좌석이 다 팔렸다. VIP 회원들의 좌석 번호들이 주어졌을 때, 사람들이 좌석에 앉는 서로 다른 방법의 가짓수를 구하는 프로그램을 작성하시오.

조건

• 입장권에 5번이 쓰여 있으면 5번 좌석에 앉아야 한다. 단, 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로는 자리를 옮길 수 있다. 
• 극장에는 “VIP 회원”들이 있다. 이 사람들은 반드시 자기 좌석에만 앉아야 하며 옆 좌석으로 자리를 옮길 수 없다.
• 첫째 줄에는 좌석의 개수 N이 입력된다. N은 1 이상 40 이하이다. 둘째 줄에는 고정석의 개수 M이 입력된다. M은 0 이상 N 이하이다. 다음 M 개의 줄에는 고정석의 번호가 작은 수부터 큰 수의 순서로 한 줄에 하나씩 입력된다.

SOL

 

문제에서 자리를 생각해줬을 때, 사람들이 하는 행동은 2가지 밖에 없다.

• 자리를 옮기지 않는다. ( 자기자신의 자리에 앉는다)
• 자리를 옮긴다.

이해를 위해서, N=1~5까지는 한 번 해보자.

이때, 표는 1번 손님부터 순서대로 입장한다고 생각해보자.

n=1	n=2	n=3	n=4	n=5
1	12 21	123 213 132	1234 2134 1324 1243 2143	12345 21345 13245 12435 21435 12354 21354 13254

 

자리를 옮기는 경우, 자리를 옮기지않는 경우로 생각해주면,

DP[n] = DP[n-1] + DP[n-2] 임을 쉽게 알 수 있다.

 

하지만, 우리가 구하는건 사람들이 좌석에 앉는 서로 다른 방법의 가짓수를 구하는 프로그램이다.

VIP석에 앉은 사람들은 자리를 옮기지 못한다.

즉, VIP석에 앉은 사람들을 제외하고, 나머지 그룹끼리 서로 자리를 옮기는 경우가 모든 방법의 가짓수이다.

문제에서 준 예시라면, DP[3] *DP[2]*DP[2]가 될것이다.

 

import sys
input = sys.stdin.readline
N= int(input().rstrip())
M= int(input().rstrip())
vips = [int(input().rstrip()) for _ in range(M)]
DP=[0]*(N+1)

DP[0] =1
DP[1] =1
DP[2] =2

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

ans=1
if M>=1:
    pre=0
    for i in range(M):
        #index slice
        # pre를 기억해줬다가, 이전 값 반영
        ans *= DP[vips[i]-1-pre]
        pre =vips[i]
    #마지막 값 반영
    ans *= DP[N-pre]
else:
    ans = DP[N]
print(ans)