백준 2302 극장 좌석 (C++)

2302번: 극장 좌석

dp를 이용한 문제이다. dp를 구하기 위해선 먼저 case 2가지를 알아야 한다. dp[N] = VIP석 없이 N명을 배치할 경우의 수라고 할때 case는 아래와 같다.

• N번 학생이 N번 자리애 앉는 경우 -> 1 ~ N - 1번 학생들이 앉는 경우 dp[N - 1]
• N번 학생이 N - 1번 자리에 앉는 경우 -> N - 1번 학생은 N번 자리에 반드시 앉아야하므로 1 ~ N - 2번 학생들이 앉는 경우 dp[N - 2]

즉 점화식은 dp[N] = dp[N - 1] + dp[N - 2]가 된다. 점화식을 이용해 N까지의 경우의 수를 구한 후 VIP석들을 기준으로 잘라 경우의 수를 구해 곱한 후 출력해주었다. 난이도에 맞지 않게 생각보다 어려웠던 문제였다. dp 유형 문제를 더 많이 풀어봐야 겠다.

#include <iostream>

using namespace std;

int N, M;
int A[40];
int dp[41];
int result = 1;

void solution() {
    dp[0] = 1;
    dp[1] = 1;
    dp[2] = 2;

    for (int i = 3; i <= N; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    int start = 1;
    for (int i = 0; i < M; i++) {
        int end = A[i];

        result *= dp[end - start];
        start = end + 1;
    }

    result *= dp[N + 1 - start];

    cout << result;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N;
    cin >> M;

    for (int i = 0; i < M; i++) {
        cin >> A[i];
    }

    solution();

    return 0;
}