백준 11509 풍선 맞추기

자기 자신보다 1이 큰 원소는 개수를 세지 않는 게 문제의 핵심이다.
구현 난이도는 매우 쉬운 편이고 난이도는 사람마다 편차가 심할 것 같다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    cin >> n;
    vector<int> arr(1000002);
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        if (arr[x+1]) {
            arr[x+1]--;
        } else {
            cnt++;
        }
        arr[x]++;
    }
    cout << cnt;
}