[C/C++] 백준 #2302 극장 좌석(동적 계획법)

#2302 극장 좌석 문제는 수학적인 원리를 이해하면 풀기 편합니다.

 

문제의 링크입니다.

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

2302번: 극장 좌석

 

극장 좌석은 일렬로 최대 40개까지 있을 수 있습니다.  이 중 몇개의 좌석은 이미 고정석으로 채워져 있을 때, 1부터 N까지의 숫자를 채우는 경우의 수를 구하는 문제입니다.  단, 모든 숫자는 자신의 자리 번호와 그 옆자리로 이동을 할 수 있지만, 고정석으로는 이동할 수 없습니다.

 

theater

 

극장 자리는 아래와 같이 표시될 수 있습니다.  고정석을 ඛ이라고 표현하면, 다음과 같이 표현할 수 있습니다.

ඛ

ඛ

고정석을 건너띄어서 앉을 수 없기 때문에 위와 같은 경우에는 4개의 칸에서 나오는 경우의 수와, 3개의 칸에서 나오는 경우의 수와 1개의 칸에서 나오는 경우의 수를 계산하면 됩니다.

$$C(1)=1$$

1개의 칸의 경우의 수가 1인 것은 당연합니다.

2개의 칸인 경우에는 2, 3개의 칸인 경우에는 3, 4개의 칸인 경우에는 5...

$$C(N)=C(N-1)+C(N-2)$$

가 되어서 사실 피보나치 수열이 됩니다.

 

이렇게 해서 좌석의 경우의 수를 모두 곱하면 됩니다.

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #2302
//        - by Aubrey Choi
//        - created at 2019-06-28
//------------------------------------------------
#include <stdio.h>

int main()
{
    int p = 1, c = 1, n, m, t;
    int f[] = { 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,
        233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 
        28657, 46368, 75025, 121393, 196418, 317811, 514229, 
        832040, 1346269, 2178309, 3524578, 5702887, 9227465, 
        14930352, 24157817, 39088169, 63245986, 102334155, 165580141 };
    scanf("%d", &n);
    scanf("%d", &m);
    while(m--)
    {
        scanf("%d", &t);
        c *= f[t-p]; p = t+1;
    }
    c *= f[n-p+1];
    printf("%d\n", c);
}