[BOJ 2302] 극장 좌석(접근법 및 시행착오 공유)

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

2302번: 극장 좌석

 

 

다이나믹 프로그래밍의 본질은, 해결하기 어려운 문제를 작은 여러 문제로 나눠서 해결하는 것이다.

 

 

 

 

우선, 난 외판원 문제를 최근에 풀어서인지, 이 문제를 보자마자 비트마스크를 조지고 싶었다..

 

 

 

 

하지만, N이 40인 이상 bitmask 연산은 더이상 사용할 수 없다.

 

 

 

 

1 << 40을 하면 오류가 발생...

 

 

 

 

자, 그렇다면 이제 할 수 있는 건, 점화식을 통해서 규칙을 발견해야 한다.

 

 

 

 

VIP를 제외하고, 우선 i명이 좌석에 앉는 가짓수를 생각해보자.

 

 

 

 

i - 1명이 좌석에 앉은 가짓수에 i명만 추가한다면, dp[i] = dp[i - 1]이다.

 

 

 

 

하지만, 문제에서 주어진 조건은, VIP석이 아닌 일반석들은 앞뒤로 자리를 이동할 수 있다고 한다.

 

 

 

 

그렇다면, dp[i] = dp[i - 1] + @ 가 필요하다.

 

 

 

 

규칙을 좀 더 명시적을 살펴보기 위해서, 직접 적어서 규칙을 관찰해보자!

 

 

 

 

i = 2

1 2 

2 1

 

 

i = 3

1 2 3

1 3 2

2 1 3

 

 

i = 4

1 2 3 4

1 3 2 4

2 1 3 4

1 2 4 3

2 1 4 3

 

 

 

여기서, i는 4명이 좌석에 앉을 수 있는 방법을 나타낸다. 누군가, i = 2일 때

 

 

 

 

1 0 2(2번 좌석은 비워두고 3번 좌석에 앉기)

 

 

 

 

를 왜 포함안시키냐고 따질 수 있지만,,,

 

 

 

 

우리가 찾아야 할 것은 모든 좌석에 빈틈없이 모든 사람이 앉아야 한다는 것이다!

 

 

 

 

자 그렇다면, 다시 본론으로 돌아와,

 

 

 

 

@의 정체를 찾아보자. @은 dp[i - 2]의 좌석을 바꿔 앉은 경우를 포함한다.

 

 

 

 

그래서 점화식은 dp[i] = dp[i - 1] + dp[i - 2]가 된다.

 

 

 

 

규칙성을 찾는 문제는, 단순히 수의 나열을 통해서 규칙을 찾는 것으로 끝나는 것이 아니라 점화식의 원리를 찾는 것이 더 중요해보인다.

 

 

 

 

해설코드(C++).

 

#include <iostream>

using namespace std;

 

int N, M, vip;

int dp[41];

int result = 1;

int tmp = 0;

 

int main() {

    cin >> N;

    

    dp[0] = 1;

    dp[1] = 1;

    dp[2] = 2;

    for(int i = 3; i <= N; i++)

        dp[i] = dp[i - 1] + dp[i - 2];

    

    cin >> M;

    for(int i = 1; i <= M; i++)

    {

        cin >> vip;

 

        result *= dp[vip - tmp - 1];

        tmp = vip;

    }

    

    cout << result * dp[N - tmp] << endl;

    return 0;

}