BOJ 2302 극장 좌석

 

문제 링크 : https://www.acmicpc.net/problem/2302

2302번: 극장 좌석

 

모든 i 에 대하여, i 번 입장권을 가진 사람이 앉을 수 있는 자리는 (i-1), i, (i+1) 일때,

입장권 번호와 다르게 앉을 수 있는 방법은 이웃하는 두 사람이 서로 자리를 바꿔 앉는 경우 뿐이다.

 

따라서 i 번까지 좌석이 배치될 수 있는 방법의 수를 dp[i] 라 하고 마지막 i 번을 기준으로 생각해보면 

1.  (i-1) 과 i 번 좌석이 바뀐 경우 -> dp[i-2]

2.  i 번 입장권을 가진 사람이 i 번 좌석에 앉은 경우 -> dp[i-1]

의 두 가지 방법으로 분해된다. 이로부터

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

를 얻는다.

 

dp[2]=2 이므로 조작적으로 dp[0]=1 로 정의한다. (이는 vip 두 사람이 이웃해 있을 때를 생각해보면 자연스럽다.)

그리고 좌석이 고정되는 vip 사이의 간격에 해당되는 dp 들의 곱이 답이 된다.

 

#include<bits/stdc++.h>

using namespace std;

int arr[41], dp[41];

int main(){
    dp[0]=1, dp[1]=1;
    for(int i=2;i<=40;i++)
        dp[i]=dp[i-2]+dp[i-1];
    
    int n,m; scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) scanf("%d",&arr[i]);
    int ans=1;
    for(int i=1;i<=m;i++){
        int t=arr[i]-arr[i-1]-1;
        ans*=dp[t];
    }
    ans*=dp[n-arr[m]];
    printf("%d\n", ans);
}