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

문제 링크입니다. https://www.acmicpc.net/problem/2302

2302번: 극장 좌석

규칙에 따라 극장을 앉을 수 있는 경우의 수를 구하는 문제입니다.

 

규칙은 다음과 같습니다.

1. X번 좌석에 앉을 때 X번만이 아닌, X±1번 좌석에도 앉을 수 있다.

2. 만약 X번 좌석이 VIP 고객일 경우 해당 좌석은 반드시 자신만 앉아야 한다.

 

다음 규칙을 따라서 VIP 고객의 번호가 주어질 때, 앉을 수 있는 경우의 수를 구해야 합니다.

 

그렇다면, 간단하게 생각해보겠습니다.

문제와 같이 좌석과 VIP 고객이 있다고 해보겠습니다.

1   2   3   4   5   6   7

그렇다면 움직일 수 있는 부분은 (1~3)과 (5~6)이 됩니다. 

따라서 총 경우는 이 두개를 곱한 값이 되는 것입니다.

 

그렇다면 1~N개까지 움직일 수 있을 때의 경우의 수가 필요합니다.

 

1개만 움직일 수 있다고 하면 -> 1개입니다.

2개만 움직일 수 있다고 하면 -> 2개입니다. (12 / 21)

3개만 움직일 수 있다고 하면 -> 3개입니다. (123 / 132 / 213)

4개만 움직일 수 있다고 하면 -> 5개입니다. (1234 / 1243 / 1324 / 2134 / 2143)

 

해당 방법과 같이 확인해보면 알 수 있는 것이 있습니다.

X번은 X-1번 + X-2번과 같은 값이 나옵니다. 

그 이유는, X-1번에 수를 하나 붙이면 X번이 되며, X-2번에 두 수를 붙이고 돌리면 X번의 경우가 되기 때문입니다.

 

이를 확인했다면 나머지는 몇개의 좌석을 움직이는 지를 알아내기만 하면 됩니다.

 

 

자세한 것은 코드를 참고해주세요.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <string>
#include <cmath>

using namespace std;

int N, M;
int arr[41];
int dp[41];
int sum = 1;

void solve(){
    dp[0] = 1;
    dp[1] = 1;
    for(int i = 2; i <= N; i++){
        dp[i] = dp[i-1] + dp[i-2];
    }
    if(M >= 1){
        sum *= dp[arr[1] - 1];
        sum *= dp[N - arr[M]];
        for(int i = 2; i <= M; i++){
            sum *= dp[arr[i]-arr[i-1]-1];
        }
    }
    else sum *= dp[N];
    cout << sum;
}

int main(){
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M;
    for(int i = 1; i <= M; i++) cin >> arr[i];
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요.