[DP] 백준 2302 극장 좌석

2 3 5 8 ... 피보나치

#include <iostream>

#include <cstring>

#include <algorithm>

#include <vector>

using namespace std;

bool vipsit[41];

long long dp[43];

void cal_part() {

       dp[0] = 1; // 이거 해주는 이유는 vip가 두번 연속 나왔을 때 0

으로 초기화 되어 있으면 값이 0이 되므로 1을 해줘도 전체적인 값에 영향은 없다 .

       dp[1] = 1;     

       dp[2] = 2;

       for (int i = 3; i <= 43; ++i) {

               dp[i] = dp[i-1] + dp[i-2];

       }

}

void print_part() {

       for (int i = 1; i <= 100; ++i) {

               cout << dp[i] << ' ';

       }

       cout << endl;

}

int main(void) {

       int n;

       cin >> n;

       int t;

       cin >> t;

       cal_part();

       //print_part();

       for (int i = 0; i < t; ++i) {

               int k;

               cin >> k;

               vipsit[k] = true;

       }

       int ans = 1;

       int cnt = 0;

       for (int i = 1; i <= n; ++i) {

               if (vipsit[i] == true) {

                      ans *= dp[cnt];

                      cnt = 0;

               }

               else {

                      cnt++;

               }

       }

       if (cnt > 0) {

               ans *= dp[cnt];

       }

       cout << ans << endl;

       return 0;

       

}// 123 4 56 7 89

    // 3 * 2 * 2