[백준 2302번] 극장 좌석 (C++)

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

2302번: 극장 좌석

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = INT_MAX;

int N, M, arr[41], dp[41];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N >> M;
    for(int i=0; i<M; i++) cin >> arr[i];

    dp[0]=1; dp[1]=1; dp[2]=2;
    for(int i=3; i<41; i++) dp[i] = dp[i-1] + dp[i-2]; //기본 점화식

    int result = 1, s = 0;
    for(int i=0; i<M; i++) 
    {
        int e = arr[i];
        result *= dp[e-s-1]; //현재~Vip 구간 곱해주기
        s = e;
    }
    cout << result * dp[N-s]; //마지막 구간 곱해주기

    return 0;
}

 

우선 기본적인 좌석에 대해 dp식을 구해준다.

dp[1] 
1 -> 1개

dp[2] 
1 2
2 1
-> 2개

dp[3]
1 2 3
2 1 3
1 3 2
-> 3개

dp[4]
1 2 3 4
2 1 3 4
1 3 2 4
1 2 4 3
2 1 4 3
-> 5개

dp[5]
1 2 3 4 5
2 1 3 4 5
1 3 2 4 5
1 2 4 3 5
2 1 4 3 5
1 2 3 5 4
2 1 3 5 4
1 3 2 5 4
-> 8개

 

위 경우의 수를 보면 규칙을 찾을 수 있다.

바로 N-1 케이스에 숫자 N을 더해주는 경우(N-1 경우의 수)와 N-2 케이스에 숫자 N의 위치를 바꿔준 경우(N-2 경우의 수) 이다.

따라서 점화식은 dp[i] = dp[i-1] + dp[i-2]가 된다.

 

이를 기반으로 Vip구간을 체크하여 Vip를 제외하고 나온 구간들에 대해 곱해준 값을 출력해주면 된다.

이를 위해 포인터를 2개 사용하여 처음~Vip 직전까지의 구간을 구해준다.

시작점은 0, 끝점은 첫 번째 Vip가 나오는 시점이다.

이를 이용해 dp[e-s-1]을 통해 Vip 전까지의 구간 dp 값을 구해준다.

다음 구간 체크를 위해 시작점을 끝점으로 옮기고, 새로운 끝점을 찾아서 위 과정을 반복한다.