[백준] 2302번 극장 좌석

문제: 2302번: 극장 좌석

basic-algo-lecture/workbook/0x10.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x10.md at master · encrypted-def/basic-algo-lecture

 

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> dp(n + 1);
    vector<int> nums(n + 1); // 0번 인덱스는 안 써(인덱스 계산 편하게 하려고..)

    while (m-- > 0) {
        int tmp;
        cin >> tmp;
        nums[tmp] = 1; // vip 표시~
    }
    
    dp[0] = { 0, 0 };
    dp[1] = { 1,0 };
    for (int i = 2; i < n + 1; i++) {
        // 내가 vip 라면?
        if (nums[i] == 1) {
            dp[i] = { dp[i - 1].first + dp[i - 1].second, 0 };
            continue;
        }

        // 내 앞이 vip 라면
        if (nums[i - 1] == 1) {
            dp[i] = dp[i - 1];
        }
        // 내 앞이 vip 가 아니라면
        else {
            dp[i] = { dp[i - 1].first + dp[i - 1].second, dp[i - 1].first };
        }
    }
    cout << dp[n].first + dp[n].second;

    return 0;
}

 

이 문제는 좌석이 vip 인 경우와 아닌 경우를 나눠서 dp 테이블을 채워야 하는 문제이다.

 

dp 테이블을 pair<int, int> 타입의 vector 로 선언했다. first 에는 자기 자신으로 끝나는 경우의 수, second 에는 그 외의 경우의 수를 저장하도록 했다.

 

만약 현재 좌석이 vip 석이라면 dp 의 값은 dp[i] = {dp[i-1].first + dp[i-2].second, 0} 가 된다. 현재 좌석이 vip 라면 다른 좌석이랑 바꾸는게 불가능 하다. 즉, 그냥 맨 마지막이 자기 자신으로 끝나게 되므로 first 와 second 를 더한 값을 first 에 놓고, second 값을 0으로 해준다. 그냥 맨 마지막에 자기 자신을 추가하는 것과 같기 때문이다. 현재 좌석이 vip 인 경우는 dp 값만 갱신해주고 continue 로 넘어가도록 했다.

 

만약 현재 좌석의 앞이 vip 석이라면 dp 의 값은 dp[i] = dp[i-1] 이다. 이유는 그냥 이전의 dp 속의 숫자 나열들에 맨 마지막에 자기 자신을 덧붙이는 것이기 때문이다. 즉, 경우의 수에 변화가 없다.

 

현재 좌석이 앞이 vip 가 아니라면 dp 의 값은 dp[i] = { dp[i - 1].first + dp[i - 1].second, dp[i - 1].first } 이다. 일단 자기자신으로 끝나는 경우의 수는 이전 dp 값의 전체 경우의 수와 같다. 자기자신으로 끝나지 않는 경우의 수는 이전 dp 값의 자기 자신으로 끝나는 경우의 수와 같다.

 

맨 마지막에 dp[n].first + dp[n].second 를 출력해주면 끝이다!_!