[Gold V] 극장 좌석 - 2302

[문제 위치]

https://www.acmicpc.net/submit/2302/64855448

[문제 풀이]

 

이 코드는 피보나치 수열을 기반으로 한 다이나믹 프로그래밍이다. 문제는 좌석을 바꾸는 경우의 수를 계산하는 것이고, 조건은 인접한 사람끼리만 자리 교환이 가능하다는 제한이 있다. 이 제한은 곧 한 칸 또는 두 칸 뒤로만 이동이 가능하다는 의미로 바뀐다. 즉, n개의 좌석에서 가능한 교환 방식의 수는 n-1개일 때와 n-2개일 때의 경우의 수를 더한 것과 같아진다. 따라서 이 문제는 계단 오르기 방식의 피보나치 점화식을 따르게 된다.

 

그러나 문제에 VIP 좌석이라는 고정 요소가 추가된다. VIP 좌석은 움직일 수 없기 때문에, 전체 좌석을 VIP 좌석을 기준으로 잘게 나누어 각 구간을 독립적으로 계산해야 한다. 각 구간은 고정된 VIP 좌석 사이의 일반 좌석들로 구성된다. 이 독립된 구간들에 대해 각각 경우의 수를 구하고, 그것들을 모두 곱하면 전체 좌석에 대한 가능한 배치 수가 된다.

#include <iostream>
 
#define MAX 45
using namespace std;
 
int N, M;
int DP[MAX];
int Vip[MAX];
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < M; i++) cin >> Vip[i];
}
 
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 Answer = 1;
    int Start = 0;
    for (int i = 0; i < M; i++)
    {
        int End = Vip[i];
        Answer = Answer * DP[End - Start - 1];
        Start = End;
    }
    Answer = Answer * DP[N - Start];
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{ 
    Solve();
 
    return 0;
}