[백준 2302] 극장 좌석

문제

www.acmicpc.net/problem/2302

 

알고리즘

DP

 

풀이

극장좌석 $N$개가 주어질 때, 앉을 수 있는 경우의 수를 묻는 문제입니다. VIP가 아닌 좌석은 좌우로 자리를 바꾸어 앉을 수 있습니다.

 

$i$번째 자리가 양 옆자리와 바꿀 수 있다고 생각하면 조금은 헷갈리는 문제입니다. $i$번째 자리가 오른쪽과 바꿔 앉는 것은 $i+1$번째 자리가 왼쪽과 바꿔앉는 경우와 일치하므로 왼쪽 좌석과 바꿀 수 있다고 문제를 생각하겠습니다.

 

$cache[i]$= $i$번째 자리까지 고려했을 때 앉을 수 있는 경우의 수

 

이는 자리를 바꿀 때 $cache[i-2]$와 자리를 바꾸지 않았을 때인 $cache[i-1]$의 합으로 나타낼 수 있습니다.

 

코드

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;

int cache[45];
int N, V, prv, ans = 1;

int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> N;
    cache[0] = cache[1] = 1;
    for (int i = 1; i < N; ++i)
        cache[i + 1] = cache[i] + cache[i - 1];

    cin >> V;
    while (V--) {
        int x;
        cin >> x;
        ans *= cache[x - prv - 1];
        prv = x;
    }
    ans *= cache[N - prv];
    cout << ans;
    return 0;
}