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

www.acmicpc.net/problem/2302

2302번: 극장 좌석

 

 

극장 좌석의 문제는 다이나믹 프로그래밍 문제로, 

수열의 규칙을 찾아보면, 피보나치 수열임을 알 수 있습니다.

 

그 원리를 이용해서 해당 구간의 경우의 수를 곱해주는 문제입니다.

 

문제에서 VIP좌석이 있지만,

일단 우리는 VIP좌석을 빼고 규칙성을 찾아봅시다.

 

VIP좌석을 빼고 규칙을 찾으면

1부터 N까지의 가능한 경우의 수는

1번째 = 1

2번째 = 2

3번째 = 3

4번째 = 5

5번째 = 8

6번째 = 13

7번째 = 21

......

N번째 = N-1번째 + N-2번째

즉, 피보나치 수열임을 볼 수 있습니다.

 

따라서, N까지의 피보나치 수열을 미리 구한다음에,

 

VIP좌석들이 있다면, 1번째부터 VIP[첫번째]좌석까지의 피보나치 수열,

VIP[첫번째좌석]~ VIP[두번째좌석] - 1의 피보나치 수열을 누적 곱을 해주면 됩니다.

 

곱해주는 이유는 각각의 경우의 수는 연관이 있기 때문에 누적 곱을 해줍니다.

 

그리고 마지막으로 N - VIP[마지막번째]의 피보나치 수열을 구해서 누적 곱을 해주면

마지막부분 까지 처리를 할 수 있습니다.

 

#include <iostream>

using namespace std;

const int MAX = 41;

int n, vipCnt;
int dp[MAX];
int vip[MAX];

void calDP(){
    dp[0] = dp[1] = 1;

    for (int i = 2; i <= n; i++){
        dp[i] = dp[i-1] + dp[i-2];	// 피보나치 수열 계산
    }
}

int calCase(){
    int res = 1;

    for (int i = 1; i <= vipCnt; i++){
        res *= dp[vip[i] - vip[i-1] - 1]; // 해당 구간 크기의 피보나치 수열 누적 곱
    }

    return res *= dp[n - vip[vipCnt]];	// 마지막vip부터 N까지 구간 피보나치 수열 구해서 누적 곱 
}
void solution(){

    cin >> n;

    calDP();	// n까지 피보나치 수열 미리 계산하기


    cin >> vipCnt;

    for (int i = 1; i <= vipCnt; i++){
        cin >> vip[i];
    }

    cout << calCase() << '\n';
    
}
int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solution();

    return 0;
}