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

극장 좌석

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

 

2024.10.23 - [Algorithms/알고리즘 문제 해결 전략] - [종만북] 알고리즘 문제를 해결하는 과정

[종만북] 알고리즘 문제를 해결하는 과정

회고의 방식을 위 포스팅의 내용을 반영하여 진행할 생각입니다😊

문제 해결 과정

1. 문제를 읽고 이해하기

1. 1번 부터 N번까지 번호를 매긴 좌석이 있다.

2. k번의 번호표를 가지고 있는 사람들은 k-1, k, k+1 세 좌석 중 한 군데에 앉을 수 있다.

3. VIP좌석은 k번 좌석에만 앉을 수 있다.

4. 배치 방법의 경우의 수를 구하라.

 

문제 조건

• 1 <= N <= 40
• 0 <= M <= N
• VIP 좌석의 입력은 오름차순

2. 재정의와 추상화

VIP는 자리의 이동이 불가능하기 때문에, 유동적으로 자리를 선택할 수 있는 값의 범위를 각각 따져보아야 한다.

예제의 예문을 통해 접근해보자.

 

범위는 1-9, VIP 좌석은 4, 7로 주어졌다.

123 |4| 56 |7| 89 (|n|는 VIP 좌석)

123의 경우의 수와 56의 경우의 수 89의 경우의 수를 각각 구하면

3 / 2 / 2 이다.

조합 공식에 따라 모든 경우의 수는 3 * 2 * 2 = 12 이다.

 

따라서 유동적인 자리의 범위를 각각 구하고 각 범위의 경우의 수에 대해 조합공식을 적용하여 풀이하는 문제라고 생각할 수 있다.

3. 계획 세우기

범위 나누기

VIP 좌석은 오름차순으로 입력이 되므로 N의 범위에서 x, y, z 3개의 좌석을 입력 받으면 아래와 같이 범위를 4개로 나눌 수 있다.

1 ... x-1 |x| x+1 ... y-1 |y| y+1 ... z-1 |z| z + 1 ... N

 

각 범위에 해당하는 경우의 수 구하기

이 문제와 비슷한 문제를 이친수라고 생각했다.

2024.09.24 - [Algorithms/백준(BOJ)] - [백준 2193] 이친수(C++)

[백준 2193] 이친수(C++)

 

K의 자리를 선택할 때, K는 이전 수의 위치에 따라 선택할 수 있는 값이 정해진다.

연속된 세 자리를 각각 X, Y, Z라 하자.

Z는 Z, Z + 1, Z - 1을 선택할 수 있다. Z + 1을 선택하는 경우는 해당 범위를 벗어나므로 생각하지 않는다.

또보나치 수열

Z - 1을 선택한 경우 Y의 경우는 Y + 1을 선택하는 경우밖에 남지 않는다.

따라서 K에서 선택할 수 있는 K의 경우의 수는 K - 1의 경우와 K - 2의 경우를 더한 값이다.

아래에 실제 값으로 확인해보자.

K가 K를 선택한 경우

 

K가 K - 1를 선택한 경우

 

4. 계획 검증하기

값의 범위에 따른 자료형 선택

N의 범위가 40까지이므로 N이 40이고, VIP 좌석이 0석일 경우 가장 큰 경우의 수를 가지게 된다.최대 경우의 수가 20억 이하라는 조건이 있기 때문에 자료형은 int로 충분하다.

 

시간 제한에 따른 알고리즘 선택

시간 제한이 2초로 널널하지만 메모이제이션을 통해 미리 계산을 해놓으면 연산을 훨씬 줄일 수 있다. 

40까지의 피보나치 수열의 값을 combination 배열에 담아놓고 VIP 좌석을 입력 받았을 때 범위에 해당하는 인덱스를 곱해준다.

피보나치 수열: O(1) / 입력 값 조회: O(M)

코드

#include <bits/stdc++.h>

using namespace std;

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

    int N, M;
    int comb[41];

    cin >> N >> M;
    comb[1] = 1;
    comb[2] = 2;
    for (int i = 3; i < 41; ++i) {
        comb[i] = comb[i - 1] + comb[i - 2];
    }
    
    int start = 1;
    int cnt = 1;
    for (int i = 0; i < M; ++i) {
        int x;
        cin >> x;
        if (x - start > 0)
            cnt *= comb[x - start];
        start = x + 1;
    }
    if (N - start + 1 > 0)
        cnt *= comb[N - start + 1];
    cout << cnt;
}

※ 오류나 개선점이 있다면 알려주세요 :) 신속히 수정하겠습니다.