[BOJ/백준][Silver1] 2302 : 극장 좌석 (C++)

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

2302번: 극장 좌석

 

 

[난이도] Silver1
[유형] DP

[풀이]
자리를 바꿀 때는 인접한 두 위치의 자리만 바꿀 수 있습니다.
예를 들어 1 2 3 이 있을 때, 세 숫자 모두 자리가 바뀌려면 3 1 2 가 되어야 하는데
3이 원래 위치에서 2만큼 떨어지게 되므로 조건을 만족하지 못하게 됩니다.

그러므로 결국 VIP석이 없는 연속된 자리가 M개 있을 때, 앉을 수 있는 경우의 수는
인접한 두 자리의 쌍을 고르는 경우의 수가 됩니다.

경우의 수가 너무 많으므로 다이나믹 프로그래밍을 이용해야 합니다.

DP[i] : 를 i개의 연속된 자리에서 앉을 수 있는 경우의 수
위와 같이 정의 했을 때,
i) 1번째 자리를 바꾸지 않은 경우
1번째 자리를 제외하고 나머지 i-1개의 자리에 대해서 DP[i-1]을 구해줘야 합니다.

ii) 1,2번째 자리를 바꾼 경우
1,2번째 자리를 제외하고 나머지 i-2개의 자리에 대해서 DP[i-2]를 구해줘야 합니다.

i,ii 두 경우의 수를 더한 것이 DP[i] 이므로
점화식은 DP[i] = DP[i-1] + DP[i-2] 인 것을 알 수 있습니다.

DP[1]~DP[N]을 미리 구해놓고
VIP 좌석간 사이에 연속된 좌석에 앉을 수 있는 경우의 수는 위의 DP 값들로 구하면 됩니다.
각 구간의 값들 곱해주면 총 경우의 수가 됩니다.

 

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
int N,M,dp[41],ans=1;
int sol(int n){
    if(n<=1) return 1;
    int& ret = dp[n];
    if(ret!=-1) return ret;
    ret=sol(n-1)+sol(n-2);
    return ret;
}
int main(){
    vector<int> v;
    scanf("%d%d",&N,&M);
    v.push_back(0);
    for(int i=0;i<M;i++) {
        int t;
        scanf("%d",&t);
        v.push_back(t);
    }
    v.push_back(N+1);
    memset(dp,-1,sizeof(dp));
    sol(N);
    for(int i=1;i<v.size();i++){
        int a = sol(v[i]-v[i-1]-1);
        if(a>0) ans*=a;
    }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver1/2302.cpp