이문제는 고등학교 때 배웠던 확률과 통계 풀이법을 사용한 문제이다. 나도 이 문제를 풀 때 어떻게 해야 할 지 막막했다. 그래서 다른 분의 풀이법을 참고했다. 일단은 vip가 없을 때 경우의 수를 해본다. 좌석이 1개일때는 1, 2개일때는 2, 3개일때는 3 대충 5까지하다보면은 규칙성이 보인다. 이걸 dp라는 배열에 dp[i]=dp[i-2]+dp[i-1] 라고 점화식을 세운다
그다음에는 vip는 고정이니깐 vip 좌석을 경계라고 두고 묶음들끼리 하면된다.
예를들면 1 2 3 vip 5 6 vip 8 9라고 하면은 (1,2,3) (5,6) (8,9)
즉 좌석이 3개일 때 경우의 수, 2개일 때 경우의 수, 2개일 때 경우의 수를 이용하는데 동시에 발생하니깐 이들을 곱해주면된다.
그래서 left를 경계의 시작 점이고 vip배열의 값이 경계의 끝점이라고 두고 위의 풀이를 이용하면 아래의 코드가 작성된다.
import sys
input=sys.stdin.readline
n=int(input())
m=int(input())
vip=[int(input()) 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-2]+dp[i-1]
total=1
if m>=1:
left=0
for i in range(m):
total*=dp[vip[i]-1-left]
left=vip[i]
total*=dp[n-left]
else:
total=dp[n]
print(total)
Back-End