BOJ : 2302 극장 좌석

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

github: https://github.com/JEONG-SEUNGWOOK/BOJ/blob/master/2302.cpp

출처

Olympiad > 한국정보올림피아드 > KOI 2005 > 초등부 3번

갓초등부의 DP(다이나믹 프로그래밍)문제다

이 문제를 자세히 들여다보면 고정석을 기준으로 좌석 수에 따른 경우의 수가 피보나치 수열을 이룬다는 것을 볼 수 있다.

#include <cstdio>
using namespace std;

long cases[41]={0,};
long ans=1;
void fibo(){
    cases[0]=1;
    cases[1]=1;
    for(int i=2;i<=40;i++)
        cases[i]=cases[i-2]+cases[i-1];   
}
int main(){
    int N,M;
    scanf("%d%d",&N,&M);
    fibo();
    int a=0, b;
    for(int i=0;i<M;i++){
        scanf("%d",&b);
        ans *= cases[b-a-1];
        a=b;
    }
    ans*=cases[N-a];
    printf("%ld",ans);
}