2302번 : 극장 좌석 [C++]

문제 풀이

성공 여부(걸린 시간): 성공(27분)

아이디어

우선 문제를 파악할 때에 어떻게 풀지에 대해서 생각을 해보았다.
일단 내가 생각한 중요한 점은 2가지다.

1. vip석을 기준으로 아닌 사람들의 무리를 나누어 줄 것
2. 해당 무리의 좌석의 조합 경우의 수를 구할 것

이 2가지를 조합하여 무리의 수에 계속 곱해나가며 결과를 출력해주면 된다.

 

그 무리의 경우의 수는 어떻게 구할까?

처음에 브루트포스처럼 일단 조합하고 갯수를 세어 진행해야하나?했으나

경우의 수가 너무 많고 무조건 시간초과가 날 것이라 생각해서
우선 각 무리의 수에 따른 경우의 수를 구해보았다.

 

무리 : 자리 조합 경우의 수
1->1
2->2
3->3
4->5
5->8

 

규칙이 보이시나요?

f(x) = f(x-1)+f(x-2) (x>2일때)

 

이러한 점화식이 나오게 된다.

 

그럼 이제 해줄 것은 작은 번호부터 제공되는 vip 좌석의 번호를 받을때마다
무리의 수를 구해주고 cnt * = dp[해당 무리의 수]를 해주면 끝이다.

!! 마지막에 N+1을 기준으로 한번 더 잘라주는 것을 잊으면 안된다.

무리의 수를 구하는 로직은 이러하다.

int cnt = 1;
int index = 0;
for (int i = 0; i <= M; i++) {
    int cut;
    if (i == M) {
        cut = N+1;
    }
    else {
        cin >> cut;
    }
    cnt *= dp[cut-1 - index];
    index = cut;
}

 

그런데 이렇게 했는데 4%에서 틀렸다고 한다.

이유는 dp[0]값을 0으로 해두었던 것이었다.

 

근데 무리가 0명인데 경우의 수가 존재합니까?

-> 아니요 존재하지 않습니다. 그러나 만약 vip좌석이 연달아 있는 경우 무리의 크기가 0으로 측정되기에

 

곱해도 이전과 같은 1로 초기화를 해두는 편이 좋다.
아니면 무리의 크기가 0일때는 곱하지 않고 넘겨도 된다.

풀이 코드

#include<iostream>
#include<vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N, M;
    cin >> N;
    cin >> M;
    vector<int> dp(41, 0);
    dp[1] = 1;
    dp[2] = 2;
    dp[0] = 1;
    for (int i = 3; i <= 40; i++) {
        dp[i] = dp[i - 2] + dp[i - 1];
    }
    if (M == 0) {
        cout << dp[N];
        return 0;
    }
    int cnt = 1;
    int index = 0;
    for (int i = 0; i <= M; i++) {

        int cut;
        if (i == M) {
            cut = N+1;
        }
        else {
            cin >> cut;
        }

        cnt *= dp[cut-1 - index];
        index = cut;
    }
    cout << cnt;
    return 0;
}