[백준] 2302번: 극장좌석

문제 링크: www.acmicpc.net/problem/2302

2302번: 극장 좌석

문제 유형: DP

백준 2302번 극장좌석 문제

접근방식:

합의 법칙 -> 두 사건이 동시에 일어나지 않을 경우 더한다.

곱의 법칙 -> 두 사건이 동시에 일어날 경우 곱한다.

참고

합의 법칙, 곱의 법칙

좌석을 옮기는 방법은 2가지다.

1. 좌석을 옮기지 않는 경우 -> dp[n-1]

2. 좌석을 옮기는 경우 -> dp[n-2]

이에 따라 점화식은 다음과 같다.

dp[n] = dp[n-1] + dp[n-2]

 

코드:

Python 3

n = int(input())
m = int(input())

vip = []
for i in range(0,m):
    k = int(input())
    vip.append(k)
sit = [1,1,2]
for i in range(3,41):
    sit.append(sit[i-2]+sit[i-1])
ans = 1
if m >= 1:
    pre = 0
    for i in range(0,m):
        ans = ans * sit[vip[i]-1-pre]
        pre = vip[i]
    ans = ans * sit[n-pre]
else:
    ans = sit[n]
print(ans)