[백준 2302] 극장 좌석 C++

문제

백준 2302 극장 좌석 C++

2302번: 극장 좌석

풀이

처음에 dp인지 완전탐색인지 헷갈렸던 문제

최대 21억 개의 가짓 수가 있는 것 보고 dp일거 같았다.

 

자신의 번호와 다른 자리에 앉을 때는, 항상 그 사람과 나의 자리를 바꿔서 앉는다는 것에 초점을 두고 고민했다.

1, 2, 3 세 명을 자리에 앉힌다고 가정하자.

1과 2, 2와 3을 서로 바꿔 앉게 할 수 있다.

 

1, 2를 먼저 앉힐 때

1 2 또는 2 1이 가능하다.

 

이 때 3을 앉힐 때

1 2 뒤에 3을 앉혀 1 2 3을 만들거나 1 3 2로 바꿔 앉을 수 있고

2 1 뒤에 3을 앉혀 2 1 3을 만들 수 있다.

 

따라서 경우의 수는 3가지다.

 

이를 일반화시키면 다음과 같다.

 

마지막 번호를 N이라고 하고 번호 n까지의 앉는 경우의 수를 result[n]이라고 하자.

1. 마지막 번호가 VIP거나 마지막 번호의 앞 번호가 VIP인 경우

마지막 사람이 자리를 바꿀 수 없으므로 그대로 앉아야 한다. 마지막 번호 전 N-1 까지의 경우의 수가 그대로 유지된다.

따라서 result[N] = result[N - 1]이다.

 

마지막 번호와 마지막 번호의 앞 번호 모두 VIP가 아니라면 자리를 바꿀 수 있다.

2-1. 자리를 바꾸지 않고 마지막 번호가 마지막 자리에 앉는 경우

마지막 번호를 끝에 앉히면 되므로 그 전 번호까지 경우의 수가 그대로 유지된다.

즉, result[N - 1]개의 경우의 수가 존재한다.

 

2-2. 마지막 사람이 그 앞 사람과 자리를 바꾸는 경우

그 앞앞사람 (3인경우 1) 까지의 경우의 수 + 마지막 사람과 그 전 사람이 자리 바꿔 앉기의 경우의 수가 가능하다.

따라서 그 전전 번호까지 경우의 수가 그대로 유지된다.

즉, result[N - 2]개의 경우의 수가 존재한다.

 

따라서 result[N] = result[N - 1] + result[N - 2]이다.

 

소스 코드

#include <iostream>
using namespace std;
 
int main()
{
    bool isVIP[41] = {};
    int result[41] = {};
 
    int N = 0;
    int M = 0;
    
    cin >> N >> M;
 
    for (int i = 0; i < M; i++)
    {
        int idx = 0;
        cin >> idx;
        isVIP[idx] = true;
    }
 
    result[1] = 1;
 
    if (isVIP[1] || isVIP[2])
        result[2] = 1;
    else
        result[2] = 2;
 
    for (int idx = 3; idx <= N; idx++)
    {
        if (isVIP[idx - 1] || isVIP[idx])
            result[idx] = result[idx - 1];
        else
            result[idx] = result[idx - 2] + result[idx - 1];
    }
 
    cout << result[N];
 
    return 0;
}