boj 2302 : 극장 좌석

boj 2302 : 극장 좌석

쉬운 DP문제. 쉬운 DP는 그만 풀어도 되는데 손이 자꾸 가네...

f(i) : vip가 없을 때 i번까지 자리를 바꿀 수 있는 경우의 수

이렇게 두면

1. i <= 1 일 때 : f(i) = 1

2. i >= 2 일 때 : f(i) = f(i - 1) + f(i - 2)

2.1 f(i - 1) : i가 가만히 있는 경우

2.2 f(i - 2) : i가 자리를 바꾸는 경우

vector에 0, vip1, vip2, ... vipM, N + 1을 담은 후

결과값은 f(N + 1 - vipM) * ... f(vip2 - vip1) * f(vip1) 을 출력.