[백준][C++] 2302번: 극장 좌석 <239>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

https://www.acmicpc.net/problem/2302

2302번: 극장 좌석

 

생각의 흐름

 

1) 일반석 1자리만 있는 경우

당연히 해당 1자리만 앉으면 끝이니 1가지 경우이다. DP[1] = 1 이 된다.

 

2) 일반석 2자리만 있는 경우

이 경우는 2가지 경우가 가능한데, 다음과 같이 가능하다.

[A][B]
[B][A]

 

3) 일반석 3자리만 있는 경우

우선 가능한 케이스를 살펴본 후 규칙성을 찾아보자.

[A][B][C]
[B][A][C]
[A][C][B]

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

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

 

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

1. [ A ] [ B ]

2. [ B ] [ A ]

 

그럼 위와 같은 2가지 경우가 나오게 되는데, 사실 이는 2번 케이스에 해당된다.

"일반석 2자리만 있는 경우"를 나타내는 것이다.

 

마지막 [A][C][B]는 C가 한칸 앞으로 이동하게 된 경우이다.

C가 중간으로 이동한 경우 B는 자동으로 맨 뒤로 가야한다. A가 맨 뒤로 갈수는 없기 때문이다.

따라서 "일반석 1자리만 있는 경우" 에 해당된다. [A] 에 뒤에 [C][B]가 붙은 것 이다.

 

따라서 점화식은 다음과 같다.

DP[i] = DP[i-1] + DP[i-2]

그럼 이렇게 구한 DP[N]의 값이 정답일까? 아니다!

 

VIP석이 숨어있기 때문이다!

출처 - https://mygumi.tistory.com/132

위 그림과 같이 vip는 무시하고 그 사이의 DP값을 구하여 전부 곱하면 된다.

곱하는 이유는 동시에 일어나는 경우이기 때문에 곱하기 연산을 해줘야 한다.

 

나의 코드

#include <bits/stdc++.h>
#include <iostream>

using namespace std;
#define MAX 41

int N, M;
int DP[MAX];
int vip[MAX];

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

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

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

    int res = 1;
    int start = 0;

    for(int i = 0; i < M; i++) {
        int end = vip[i];
        res = res * DP[end - start - 1];
        start = end;
    }
    res = res * DP[N - start];
    cout << res;

    return 0;
}