[백준] 2302번 극장 좌석 C++

문제 출처: https://www.acmicpc.net/problem/2302

2302번: 극장 좌석

 

 

현재 idx번 좌석을 그대로 앉는 경우의 수는 chair(idx+1)으로 계산되고

현재 idx번 좌석과 idx+1번 좌석을 서로 바꾼 뒤 앉는 경우의 수는 chair(idx+2)으로 계산된다.

(좌석은 서로 바꿔야 하기 때문에 idx와 idx+1을 바꿨다면 그 다음은 idx+2부터 계산해야 하기 때문)

점화식으로 풀면 chair(idx) = chair(idx+1) + chair(idx+2)이다. dp배열을 사용하여 메모이제이션을 해주며 Top-Down방식으로 풀었다.

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include <string>

using namespace std;

int fix[41];
int N;
int dp[41];

int chair(int idx) {
    if (idx == N+1)return 1;
    if (dp[idx] != -1)return dp[idx];
    if (fix[idx] == 1) { return chair(idx + 1); }
    

    //자기 자리에 그대로 앉는다.
    int val = chair(idx + 1);

    //다음 자리가 있다면 (현재 idx가 끝이 아니라면)
    if (idx + 1 <= N) { 
        //다음 자리가 FIX 석이 아니라면
        if(fix[idx+1]!=1)
            //현재 좌석과 다음 좌석을 바꾼다.
            //현재좌석과 다음 좌석이 확정되었으므로 다다음 좌석으로 이동
            val = val + chair(idx + 2); 
    }
    dp[idx] = val;
    return val;
}



int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    fill(&dp[0], &dp[41], -1);
    cin >> N;


    int M;  cin >> M;
    for (int i = 1; i <= M; i++) {
        int temp;
        cin >> temp;
        fix[temp] = 1;
    }

    cout << chair(1);
    

}