2302 극장 좌석

#include <stdio.h>
 
int main() {
    int total, n;
    scanf("%d %d", &total, &n);
 
    int len_num[50] = { 0 }, bef = 1;
    while (n--) {
        int cur;
        scanf("%d", &cur);
 
        int len = cur - bef;
        len_num[len]++;
 
        bef = cur+1;
    }
    len_num[total - bef + 1]++;
 
    int maxV = -1;
    for(int i=40;i>0;i--)
        if (len_num[i] > 0) {
            maxV = i;
            break;
        }
    
    int dp[50] = { 0 };
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= maxV; i++) 
        dp[i] = dp[i - 1] + dp[i - 2];
    
    int rst = 1;
    for (int i = maxV; i > 0; i--) {
        int num = len_num[i];
 
        for (int j = 1; j <= num; j++) {
            rst *= dp[i];
        }
    }
 
    printf("%d", rst);
}

1. 각 좌석을 vip 석을 기준으로 얼만큼의 간격이 있는지 먼저 구한다

2. 각 좌석의 간격 길이에 대응되는 DP 값을 구한다

> dp[i] = i 번째 좌석에 그대로 앉는 경우 + (i-1)번째 좌석에 그대로 앉는 경우

3. 각 간격의 DP 값들을 서로 곱해준다