Baekjoon - Seats in Theater

Baekjoon : Seats in Theater

Description

There is theater with seats in one line ranging from 1 to N. Audience must take a seat according the number on the ticket. However, they may take a seat to their left or right (i.e. - audience with ticket number 5, may sit either in seat 3 or 4). On the other hand, the VIPs can only sit in the given number and are not allowed to change their seats in any case. Following this constraints, return the number of cases which audience can sit differently.

Example

When N = 9, VIP = 4 & 7

• <123456789> (O)
• <213465789> (O)
• <132465798> (O)
• <312456789> (X)
• <123546789> (X)

Input

9 // 1 <= N <= 40
2 // Number of VIP seats, M 
4 // Vip Seat
7 // Vip Seat

Output

12

Approach

The number of cases for each consecutive seats shares a same pattern to Fibonacci Sequence

• 1, [2] => Possible Case (1)
• 1, 2, [3] => Possible Cases (1, 2) and (2, 1)
• 1, 2, 3, [4] => Possible Cases (1, 2, 3, 4) , (1, 2, 4, 3), (2, 1, 3, 4), (2, 1, 4, 3), (1, 3, 2, 4)

Solution (C++)

#include <iostream>
using namespace std;

int N, M, vip; 
int result = 1, current = 0; 
int dp[41] = {1, 1};

void fib()
{
    for (int i = 2; i < 41; i++)
    {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
}

int main()
{
    fib();

    cin >> N;
    cin >> M;
    
    for (int i = 0; i < M; i++)
    {
        cin >> vip;
        result = result * dp[vip - current - 1];
        current = vip;
    }

    result = result * dp[N - current];

    cout << result << "\n";
}