[BOJ-2302]극장좌석

처음에 접근 방법은 

일렬로 좌석이 배치되어있으므로 

1. 해당 좌석 자리(i)에서 -1칸 (i-1) 칸으로 이동하는 경우

2. 해당 좌석 자리(i)에서 그대로 있는 경우

3. 해당 좌석 자리(i)에서 +1칸 (i+1) 칸으로 이동하는 경우로 생각했었다.

그런데 이경우를 보니 

vip좌석(움직이지 못하는 좌석)을 제외하고 접근하였다. 

vip 좌석이 없는 경우라고 가정하고서 

① 1 만 있는 경우

에는 자기 자리 밖에 못 앉는다. 그러므로 경우의 수는 1 이다.

② 1 2 가 있는 경우

에는 그대로 자기 자리에 앉거나, 둘이 자리를 바꾸는 경우 각각 더해서 2가지 경우가 된다.

③ 1 2 3 이 있는 경우

에는 1을 그대로 두면 ②의 경우가 발생한다. 

이때 2 1 을 바꾸어 앉는 경우가 발생할 수 있으므로, ①의 경우가 발생한다. 

그러므로, ① + ② 의 경우이다.

④ 1 2 3 4 가 있는 경우

1을 그대로 두는 경우 2 3 4 를 바꾸는 경우인 ③ 이 발생한다.

2 1 을 바꾸어 앉으면 ② 의 경우가 발생한다. 

그러므로 ② + ③ 의 경우이다. 

⑤ 1 2 3 4 5 가 있는 경우 

⑤ 의 경우도 마찬가지로 1을 그대로 두는 경우 1, 2를 교환해서 앉는 경우가 발생한다. 

그러므로 ③ + ④ 이다.

결국에는  의 피보나치 공식이었다.

이제 문제의 조건인 vip 좌석(움직이지 못하는 좌석)을 추가 하였다. 

예제로 생각했을 때 

1 2 3 4 5 6 7 8 9 가 있었고, 4와 7의 자리가 vip 좌석이다. 

이런 경우가 되는 것인데, 이때 자리를 스왑할 수 있는 칸이 각 3개, 2개, 2개 있다는 말이다. 

 

그럼 이때 그 경우들을 곱하면 답이 될 거라고 생각하고 코드 작성했다

#include<cstdio>
#define MAX 55
typedef long long ll;
ll dp[MAX] = {1,1}; 
int idx[MAX];
void dy(){
    for(int i = 2 ; i < MAX ; i++){
        dp[i] = dp[i-1] + dp[i-2];
    }
}
int main(){
    dy();
    int n; scanf("%d", &n);
    int vip; scanf("%d", &vip);
    
    ll res = 1;    
    idx[vip+1] = n+1;
    for(int i = 1 ; i <= vip ; i++) scanf("%d", &idx[i]);
    for(int i = vip+1 ; i >= 1 ; i--){
        idx[i] = idx[i] - idx[i-1] - 1;
        res *= dp[idx[i]];
    }
    printf("%lld",res);
    return 0;
}