[2302번] 극장 좌석

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

2. 수학

이 문제는 그림으로 그려보니 해결 할 수 있는 문제였다.

vip가 아무도 없다고 가정하고 

1만 있다면 경우의 수가 1

1,2가 있다면 경우의 수가 2

1,2,3이 있다면 경우의 수가 3

1,2,4가 있다면 경우의 수가 5

.

.

.

1,2,4,...,8,9가 있다면 경우의 수가 55이다.

즉, vip가 없는 경우에는 피보나치 수를 따른다.

이를 이용해서 이 문제를 접근해보자.

result라는 값과, left라는 값을 둔다

arr[pos - left - 1]의 의미는

pos는 일단 vip위치를 의미한다.

예제대로 4가 입력되어

arr[4- 0 - 1] = arr[3]이 되는데

arr[3]의 의미는 vip 4번자리에서 왼쪽 기준으로 3자리가 있다는 의미이고, 3개의 수가 있을 때 피보나치는 3이다.

따라서 result *= 3이 된다.

그다음 7번이 vip이니

arr[7 - 4 - 1] = arr[2]가 된다.

이 의미 또한 vip 4와 vip 7사이에는 2명의 자리가 있으니 2개의 수가 있을 때의 피보나치는 2이다.

따라서 result *= 2가 된다.

마지막 처리는 7에서 오른쪽 나머지 사람들에 대한 피보나치 값도 이용해야 하니

n - left로 지정하고, arr[9 - 7] = arr[2] 즉, 7번 vip자리 오른쪽으로 2자리가 있으니 이에 대해서도 곱해주면 해결 할 수 있다.

소스 코드 : 

#include <iostream>
#include <cstdio>
 
using namespace std;
 
int arr[42];
 
int main()
{
    int n, m;
    scanf("%d", &n);
 
    for (int i = 0; i <= n; i++)
    {
        if (i == 0 || i == 1)
            arr[i] = 1;
 
        else
            arr[i] = arr[i - 1] + arr[i - 2];
    }
 
    scanf("%d", &m);
 
    int result = 1;
    int left = 0;
 
    for (int i = 0; i < m; i++)
    {
        int pos;
        scanf("%d", &pos);
 
        result *= arr[pos - left - 1];
        left = pos;
    }
 
    result *= arr[n - left];
 
    printf("%d", result);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>