백준 2302 극장 좌석

백준 2302 극장 좌석

---

오늘은 극장 좌석이라는 문제를 풀어보았다. 우선 간단하게 dp 배열을 만들면 되는데, dp 규칙은 간단한 dp[n] = dp[n-1] + dp[n-2] 이다.

이제 VIP 좌석을 기준으로 그 사이의 좌석들이 조합될 수 있는 가짓수가 바로 dp 이므로,
VIP 좌석들을 기준으로 그 좌석 갯수만큼의 dp 값들을 계속 곱해주면 된다.

• 예외 처리 : VIP 좌석 갯수와 전체 좌석 갯수가 같을 때 처리해 주어야함.

#include <iostream>
#include <vector>

using namespace std;

long long int dp[42];
int main()
{
    int n, m;
    vector<int> vips;
    long long int ans = 1;

    cin>>n;
    cin>>m;
    vips.push_back(0);
    if (n == m)
    {
        cout<<"1\n";
        return 0;
    }
    for(int i = 0; i < m; i++)
    {
        int tmp;
        cin>>tmp;
        vips.push_back(tmp);
    }
    vips.push_back(n+1);

    dp[0] = 1;
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 3;
    for (int i  = 4; i <=n; i++)
    {
        dp[i] = dp[i-1] + dp[i-2];
    }

    for (int i = 1; i< vips.size(); i++)
    {
        int diff = vips[i] - vips[i-1] -1;
        ans *= dp[diff];
    }
    cout<<ans<<"\n";
    return 0;
}