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

백준의 극장좌석(2302) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

문제에 조건에 맞게 좌석을 옮겨 앉을 수 있을 때, 전체 N개의 좌석을 앉을 수 있는 경우의 수를 구해야 하는 문제이다.

문제에서는 A번째 좌석에 배정된 사람은 A - 1번 혹은 A + 1번 좌석으로 옮겨 앉을 수 있다고 되어있다.

그럼, 문제를 해결하기 전에, VIP석이 아닌, 일반석에 대해서 앉을 수 있는 경우의 수들만 한번 계산을 해보자.

지금부터 간단한 수식을 통해서 위의 경우의 수를 표현해보자.

F[A] = B 라는 수식을 사용할 것인데, "좌석이 A개 있을 때, 앉을 수 있는 경우의 수는 총 B가지 입니다." 를 의미

한다.

#Case1 : 일반석이 1자리가 있는 경우

극단적으로 예를 들어보면 다음과 같은 경우이다.

.

위의 그림에서 왼쪽 그림 같은 경우는 A번 좌석 양쪽에 VIP 좌석이 있기 때문에 A - 1번 혹은 A + 1번 좌석으로 옮겨 앉을 수가 없는 상황이다. 왜냐하면 VIP 고객들은 VIP고객에게 배정된 그 자리에만 앉을 수 있기 때문에, A번 좌석에 배정 받은 사람이 옮겨 앉을 수가 없다.

오른쪽 그림 같은 경우는 전체 좌석의 수(N)가 1인 경우이다. 즉 ! 옮겨앉을 좌석이 존재하지 않는 경우이다.

따라서 위의 2가지 경우는 모두 "일반석에 자리가 1자리만 존재하는 경우"를 의미한다.

이 경우에, 앉을 수 있는 경우의 수는 ?? 1가지이다.

F[1] = 1

#Case2 : 일반석이 2자리가 있는 경우

.

위의 그림과 같이 일반석이 2자리가 있는 경우를 한번 살펴보자.

일반석이 2자리가 있을 때, 앉을 수 있는 경우는 다음과 같은 경우들이 존재한다.

1. [ A ] [ B ]

2. [ B ] [ A ]

이렇게 그대로 순서대로 앉거나, 아니면 A와 B가 서로 자리를 바꿔서 앉은 방법 총 2가지가 존재한다.

F[2] = 2

#Case3 : 일반석이 3자리가 있는 경우

.

먼저, 앉을 수 있는 경우를 모두 적어보자.

1. [ A ] [ B ] [ C ]
2. [ B ] [ A ] [ C ]

3. [ A ] [ C ] [ B ]

위와 같이 3가지 경우가 존재한다.

[ B ] [ C ] [ A ] 와 같은 경우는, 'A'가 A + 1, A - 1이 아닌 좌석에 배정되었기 때문에 올바르게 앉은 경우가 아니다.

따라서 가능한 경우는 위와 같이 3가지가 발생한다.

그럼 여기서 그냥 끝내지 말고 하나의 특징을 한번 알아보자.

먼저, 1번 경우 2번 경우를 살펴보자.

1번과 2번 경우의 공통점을 찾는다면 뭐가 있을까 ?? 바로 'C'가 자리를 옮기지 않았다는 공통점이 존재한다.

그럼 'C'가 자리를 옮기지 앉았으니, 'C'를 고정 시켜놨다고 생각하고 앞에 A 와 B에 대해서만 적어보자.

1. [ A ] [ B ]

2. [ B ] [ A ]

그럼 위와 같은 2가지 경우가 나오게 되는데, 어디서 많이 봤던 그림이다.

바로 위의 2가지 경우는 F[2]일 때, 즉, 우리가 위에 Case2에서 진행했던, "일반석에 좌석이 2개가 있을 때, 앉을 수 있는 경우들" 을 나타내는 것이다.

그럼 3번 경우를 한번 보자. 3번 경우는 1번,2번경우들과는 다르게,'C'가 자리를 옮긴 경우이다.

그럼, 'C'를 자리를 옮긴 곳에 고정 시켜놨다고 생각하고 그 앞에 있는 좌석들만 한번 적어보자.

1. [ A ]

이렇게 하나가 나오는데, 이 또한 우리가 위에서 많이 봤던 그림이다.

바로 F[1]일 떄, 우리가 위에 Case1에서 진행했던, "일반석에 좌석이 1개가 있을 때, 앉을 수 있는 경우"를 나타낸 것이다.

따라서, 보다 일반화된 식으로 나타내보면 F[3] = F[2] + F[1] 로 나타낼 수가 있다.

그럼, 위의 식(F[3] = F[2] + F[1]) 에서 '3'을 'N'으로 바꿔서 표현해보자.

그럼, F[N] = F[N - 1] + F[N - 2]가 된다.

위의 수식을 다시한번 이해해보고 정리해보자.

# 좌석이 N개가 있을 때 앉을 수 있는 경우의 수

1. N번째 좌석을 움직이지 않고, 그대로 N번째 좌석에 앉는 경우

- 남은 N - 1개의 좌석에 대해서 앉을 수 있는 경우의 수 만큼 경우의 수를 가지게 된다. 즉 ! F[N - 1]만큼의 경우의 수를

  가지게 된다.

2. N번째 좌석을 움직여서 앉는 경우

- N - 1번 좌석에 앉히고, 그 전에 N - 2개의 좌석에 대해서 앉을 수 있는 경우의 수 만큼 경우의 수를 가지게 된다.

  즉 ! F[N - 2]만큼의 경우의 수를 가지게 된다.

따라서, F[N] = F[N - 1] + F[N - 2] 가 된다.

그럼 위의 수식이 맞는지 좌석이 4개일 때를 예시로 확인해보자.

.

먼저, 'D'를 기준으로 'D'가 좌석을 옮기는 경우와 옮기지 않는 경우를 나눠서 적어보자.

1. 'D'가 좌석을 옮기지 않는 경우

1 - 1) [ A ] [ B ] [ C ] [ D ]

1 - 2) [ A ] [ C ] [ B ] [ D ]

1 - 3) [ B ] [ A ] [ C ] [ D ]

2. 'D'가 좌석을 옮기는 경우

2 - 1) [ A ] [ B ] [ D ] [ C ]

2 - 2) [ B ] [ A ] [ D ] [ C ]

위와 같이 5가지 경우가 존재한다.

마찬가지로 한번 더 이야기해보면, 먼저 'D'가 좌석을 옮기지 않는 경우를 보면 'D'를 저 마지막 자리에 고정시켜놨다고 생각하고 앞 좌석들에서 나올 수 있는 경우들만 적어보면...

[ A ] [ B ] [ C ]

[ A ] [ C ] [ B ]

[ B ] [ A ] [ C ]

이렇게 3가지가 있는데, 이 3가지 역시 우리가 위에서 Case3에서 진행했던 F[3]의 경우들이다.

두 번째로, 'D'가 좌석을 옮기는 경우를 보자. 'D'가 저렇게 좌석을 옮기게 됨으로써, 또 한명 자동적으로 고정이 되는 좌석이 하나 더 있다. 바로 , 'C'이다. 'D'가 좌석을 옮겼기 때문에, 'C'도 자연스럽게 좌석을 옮기게 되고, 다른 곳으로 움직일 수가 없게 된다. 그럼 'C'와 'D'는 움직일 수 없으니 고정되었다고 생각하고 나머지 좌석들만 적어보면

[ A ] [ B ]

[ B ] [ A ]

이렇게 2가지 경우가 발생하는데, 이는 우리가 Case2에서 계산한 F[2]의 값이다.

실제로, F[4] = F[3] + F[2] = 3 + 2 = 5가 된다.

즉 ! 좌석이 N 개 일 때, 앉을 수 있는 경우의 수는 F[N] = F[N - 1] + F[N - 2]가 된다.

이런 특징을 갖는 수열이 하나 있는데, 바로 피보나치 수열이다. 즉 ! 우리가 좌석에 앉을 수 있는 경우의 수는 피보나치 수열을 따르고 있다는 것을 알 수가 있다.

그럼 ! 지금까지 이걸 왜했을까?? 문제에서 주어지는 좌석이 N개라고 하면, F[N]을 구하면 정답이 나올까 ??

절대 그렇지 않다. 왜냐하면 VIP석은 좌석을 움직일 수 없기 때문이다.

그럼 이제부터는 지금까지 위와 같은 내용을 했던 이유를 알아보자.

문제에서 N이 굉장히 큰 수이고, 다음과 같은 예시가 주어졌다고 생각해보자.

.

우리에게 위와 같은 예시가 주어졌다.

어떻게 구해야할까 ?? 너무나도 간단하다. 왜냐하면 우리는 'x개의 좌석이 있을 때, 앉을 수 있는 경우의 수'를 위에서 모두 계산해 놓았기 때문이다.

위의 경우는 발생할 수 있는 경우의 수가 F[A] * F[B] * F[C] 일 것이다.

동시에 일어나는 경우들이기 떄문에 모두 곱해주어야 모든 경우의 수가 나오게 된다.

즉 ! 우리는 다음과 같이 3가지 경우들에 대한 좌석의 갯수만 계산을 해주면 된다.

1. 시작점 ~ 첫 VIP석 사이 일반석의 갯수.

2. VIP석과 VIP석들 사이 일반석의 갯수.

3. 마지막 VIP석과 마지막점 사이 일반석의 갯수.

위와 같이 3가지 경우들에 대해서 "일반석의 갯수"만 구할 수 있다면, 결과값은 우리가 위에서 했던 '피보나치 수열'을 이용해서 바로 구해낼 수가 있다.

물론 위에서 말한 2번 경우(VIP석과 VIP석 사이 일반석의 갯수)는 굉장히 여러개가 존재할 수도 있다.

그 경우들에 대해서만 모두 계산을 해주면 된다.

[ 소스코드 ]

#include <iostream>
 
#define endl "\n"
#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)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}