백준 2302 - 극장좌석

이번 문제는 백준의 실버 1 극장 좌석 문제이다.
문제를 차근차근 한 번 읽어보자.

지정된 번호에 맞는 자리에 앉아야 하나, 바로 옆으로는 옮길 수 있다.
하지만 VIP 석에 앉는 사람은 반드시 지정 좌석에만 앉아야 한다.
이 때 앉을 수 있는 모든 좌석의 경우의 수를 구해달라고 한다.

DP(Memoization)

모든 경우의 수를 구해달라고 하니, 메모이제이션이 떠오른다.
좌석이 하나일 때, 둘일 때, … , N개일 때를 한 번 구해보자.

  • 좌석이 하나일 때
    • 하나의 경우 밖에 없다.
  • 좌석이 둘일 때
    • 1 2 2 1 두 가지 경우가 있다.
  • 좌석이 셋일 때
    • 1 2 3 2 1 3 1 3 2 세 가지 경우가 나온다.

세 개까지 진행했을 때, 뭔가 규칙이 살짝 보이는 것 같다.
1 2와 2 1은 둘일 때 였고, 1은 하나일 때 였다.
확신하긴 이르니, 네 개까지 진행을 해보자.

  • 좌석이 넷일 때
    • 1 2 3 4 2 1 3 4 1 3 2 4
    • 1 2 4 3 2 1 4 3
    • 위와 같이 다섯 가지의 경우가 가능하다.

이젠 확신을 할 수 있을 순간이다.
1 2 3 2 1 3 1 3 2에 4가 붙었다.
1 2와 2 1에 3 4와 4 3이 붙었다.
그렇다 이는 F[n] = F[n-1] + F[n-2]를 점화식으로 한다.
이는 바로 유명한 피보나치 수열의 점화식이다.

그럼 이제 바로 경우의 수를 구하면 된다!
가 아니라 VIP 좌석이 껴있는 경우도 생각해야 한다.

VIP 좌석?

VIP 좌석이 껴있는 경우는, 해당 좌석은 고정석이 된다.
즉 경우의 수에 포함되지가 않는 자리이다.
그럼 우리는 VIP 석을 기준으로 그룹을 묶을 수 있다.
각 그룹들의 경우의 수를 곱해주면? 최종 경우의 수가 나올 것이다.

나는 아래의 코드와 같이 구현했다.

void init_basis() {
    seats[0] = 1;
    seats[1] = 1;
    seats[2] = 2;
    // 피보나치 수열의 초항과 같다
    vips[num + 1] = 9;
    // 마지막을 강제로 vip로 만든다.
}

int main() {
    cin >> num >> vip_num;
    for (int i = 0; i < vip_num; i++) {
        cin >> vip_seat;
        vips[vip_seat] = 9;
        // VIP 좌석을 9로 표현하자.
    }

    init_basis();
    // 주어진 의자까지의 결과를 우선 모두 저장해놓자.
    for (int i = 3; i <= num; i++)
        seats[i] = seats[i - 1] + seats[i - 2];

    int partial = 0;
    
    for (int i = 1; i <= num + 1; i++) {
    // num + 1번째 좌석은 반드시 VIP이다.
    // 그래야 마지막 구간도 계산이 가능!
        if (vips[i] == 9) {
            answer *= seats[partial];
            partial = 0;
            continue;
        }

        partial++;
    }
    
    cout << answer;
    return 0;
}

먼저 좌석 개수 별로 피보나치 수열을 구해놓는다.
그리고, VIP 좌석이 나올 때 까지 좌석의 수를 카운팅한다.
VIP석 까지의 일반 좌석 수만큼 경우의 수를 정답에 곱한다.

이 때, 중요한 것은 강제로 마지막에 VIP 석을 끼워 넣는다.
이는 남는 좌석을 계산에 끼워넣기 위함이다.