백준 2302번 극장 좌석 C++

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

2302번: 극장 좌석

 

 문제 풀이

 이 문제에서는 좌석들의 정보(VIP여부)가 주어졌을 때 가능한 모든 좌석 배치의 경우의 수를 묻는 문제이다. 

 

 당연히 VIP 좌석 때문에 나눠진 좌석들끼리는 서로 영향을 주지 못하기 때문에 각각의 경우의 수를 구하고 곱해야겠다는 생각을 했다. 또 이 가능한 경우의 수는 DP를 이용하면 쉽게 구할 수 있었다. n명의 사람이 있고, VIP가 없을 때 가능한 좌석 배치를 D[n]이라고 하면, 처음 1과 2가 자리를 바꿀 때 나머지 남은 사람이 n-2명이므로, D[n-2]이고, 처음 1과 2가 자리를 바꾸지 않을 때는 1을 제외하면 n-1명이므로 D[n-1]이다.

D[n] = D[n-1] + D[n-2] (n>2)
           2  (n=2)
           1  (n=1)    

 

  따라서 다음과 같은 아주 간단한 점화식을 얻을 수 있다. 이제 이 점화식을 이용하면 쉽게 구할 수 있다. 문제에 나온 예시로 설명을 하면,

 1~3좌석 까지는 D[3]의 경우의 수, 5~6까지는 D[2], 8~9까지도 D[2]의 경우의 수를 가지므로 답은 D[3] x D[2] x D[2] = 12가 된다.

 

 시행착오

예제로 컴파일 해봤을 때 잘 나와서 바로 채점해봤더니 틀렸다고 나와서 무척 당황했다. 근데 저번에 볼 모으기 때 했던 실수 덕분에 어디서 잘못되었는지 바로 찾을 수 있었다. 원래 코드에서는 D[0]를 그냥 0으로 두었는데, 

for(int i=1; i<=N+1; i++)
    {
        if(!SVIP[i])
        {
            k++;
        }
        else
        {
            nc *= D[k];
            k = 0;
        }
    }

 그렇게 되면 이 부분에서 만약 VIP좌석이 연속해 있을 때 전체 경우의 수 nc에 D[0]=0 이 곱해져서 값이 잘못 나오게 되었다. 그래서 D[0]을 1로 설정했어야한다.

 

 코드

#include <iostream>
using namespace std;

int main() {
    int D[41]={0,},N,M,VIP,nc=1,k=0;
    bool SVIP[42] = {false,};
    
    cin>>N;
    
    D[0] = 1;
    D[1] = 1;

    for(int i=2; i<=N; i++)
    {
        D[i] = D[i-1] + D[i-2];
    }
    
    cin>>M;
    while(M--)
    {
        cin>>VIP;
        SVIP[VIP] = true;
    }
    
    SVIP[N+1] = true;
    
    for(int i=1; i<=N+1; i++)
    {
        if(!SVIP[i])
        {
            k++;
        }
        else
        {
            nc *= D[k];
            k = 0;
        }
    }
    
    cout<<nc;
}