[ 백준 / C++ ] 2302 : 극장 좌석

[ 문제 ]

 

2302번: 극장 좌석

 

[ 접근방법 ]

 

DP를 활용하여 O(N) 만에 문제를 해결할 수 있다.

 

dp[ i ] = 연속한 i개의 좌석에 사람이 앉을 수 있는 경우의 수.

 

vip 회원 좌석을 기준으로 미리 계산한 dp[ i ]를 곱해주면 된다.

 

[ 소스코드 ]

 

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    vector<int> dp(n + 1, 0), vip(m + 1, 0);
    for(int i = 1; i <= m; i++)cin >> vip[i];

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

    int ans = 1;
    for(int i = 1; i <= m; i++){
        ans *= dp[vip[i] - vip[i - 1] - 1];
    }
    ans *= dp[n - vip[m]];

    cout << ans;

    return 0;
}