[2302] 극장 좌석

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

2302번: 극장 좌석

<문제>

점화식은 피보나치와 같은 dp[i] = dp[i-2] + dp[i-1]

고정석을 기준으로 나뉘는 M+1개의 구역들은 서로 독립적이므로

길이 3의 구역이라면 dp[3], 길이 7의 구역이라면 dp[7]을 계속 곱해주면된다.

특별히 주의할점이라면 ans=1로 넣어두는점, 마지막에 대한 off by one만 주의하면 된다

길이는 해당 구역의 시작점이 s라고 하고, 그 다음 고정석이 x라하면

[s, x-1]의 길이는 (x-1) - s + 1 == x-s 가 되겠다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n, m, dp[41];
int main(void) {
    cin >> n >> m;
    int i;
    dp[0] = dp[1] = 1;
    for (i = 2; i <= 40; i++) dp[i] = dp[i - 2] + dp[i - 1];
    int ans = 1, s = 1;
    while (m--) {
        int x;
        cin >> x;
        ans *= dp[x - s];
        s = x + 1;
    }
    cout << ans * dp[n + 1 - s];
    return 0;
}