BOJ 2302번 극장 좌석

BOJ : https://www.acmicpc.net/problem/2302

2302번: 극장 좌석

github : https://github.com/junho0956/Algorithm/tree/master/2302/2302

 

재귀로 풀어보고 싶어서 dfs로 여러번 시도해봤는데

역시 실력이 안되는 것 같다..

그냥 간단하게 vip 석이 아닌 부분의 모든 경우를 곱해서 해결하였다.

 

#include <iostream>
using namespace std;
 
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    int n, m, sum = 1;
    int arr[41];
    int dp[41] = { 1, 1, 2, };
    cin >> n >> m;
    if (m == 0) {
        for (int i = 3; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
        cout << dp[n];
    }
    else {
        int start = 1;
        while (m--) {
            int idx; cin >> idx;
            for (int i = 3; i <= idx - start + 1; i++) dp[i] = dp[i - 1] + dp[i - 2];
            sum *= dp[idx - start];
            start = idx + 1;
        }
        if (start < n) {
            for (int i = 3; i <= n - start + 1; i++) dp[i] = dp[i - 1] + dp[i - 2];
            sum *= dp[n - start + 1];
        }
        cout << sum;
    }
 
    return 0;
}