백준 2302번 극장 좌석

🔒[문제 url]

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

🪄전체 코드

#include <iostream>
#include <vector>
using namespace std;

int n,m;
vector<pair<int,int>> dp(41);
bool fix[42];

void INPUT()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i = 0; i < m; i++)
    {
        int seat; cin >> seat;
        fix[seat] = true;
    }
}


void SOLVE()
{
	//dp[i] : 1번부터 i번 좌석까지만 앉힐 경우의 최댓값
    dp[0] = {1,0}; dp[1] = {0,1};
    // dp[i].first : dp[i-2]의 값
    // dp[i].second : dp[i-1]의 값
    
    /*
    현재 i+1은 고려하지 않으므로,
    입장권 번호가 i인 회원이 앉는 좌석은 (i-1) or (i) 둘 중 하나이다.
    
    1) i-1번 좌석에 앉는 경우 : dp[i-2]
    2) i번 좌석에 앉는 경우 : dp[i-1]
    즉, dp[i] = dp[i-2] + dp[i-1]이 됨을 알 수 있다.
    
    i번 좌석이 VIP석인 경우, 앉는 사람이 고정되므로
    dp[i] 값은 변하지 않고 dp[i-1] 값을 그대로 갖게 된다.
    
    또한 k-1번 좌석이 VIP석인 경우, 아직 i+1번 좌석은
    고려하지 않으므로 dp[k] = dp[k-1]이 된다.
    */

    for(int i = 2; i <= n; i++)
    {
        if(!(fix[i-1] || fix[i]))
            dp[i] = {dp[i-2].first+dp[i-1].first,
                     dp[i-2].second+dp[i-1].second};
        else dp[i] = dp[i-1];
    }

    cout << dp[n].first + dp[n].second;

}

int main()
{
    INPUT();
    SOLVE();
}

🥇문제 후기

GOLD5 미만 난이도는 알고리즘 및 풀이 설명을 주석으로 대체합니다.
주석을 참고해주세요.