[백준] 2302번 극장 좌석

문제 링크: https://www.acmicpc.net/problem/2302

문제

입출력

문제 접근

dp문제이고, 규칙이 있는 문제였다.
해당 규칙은 피보나치 수열이였다.
그래서 미리 숫자만큼 피보나치 수열의 값을 구하고,
VIP들 사이가 끼어있는 구간의 크기를 구하여서, 해당 크기의 피보나치의 수열의 값을 구하고, 다른 구간의 값과 곱해준다.

코드 구현(c++)

#include <iostream>

using namespace std;

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

    int cache[41];
    cache[0] = 1;
    cache[1] = 1; cache[2] = 2;
    int N, M;
    cin >> N >> M;
    for(int i = 3 ; i <= N ; i++){
        cache[i] = cache[i-1] + cache[i-2];
    }
    int temp;
    int result = 1;
    int prev = 0;
    while(M--){
        cin >> temp;
        result *= cache[temp - prev - 1];
        prev = temp;
    }
    result *= cache[N - prev];
    cout << result << "\n";
}