백준 - 11509번 : 풍선 맞추기 (C++)

풀이 방법 : 그리디

화살을 쏘고 풍선을 맞췄다면 화살의 높이가 1씩 낮아진다.
만약에 높이 4인 풍선을 맞추려고 한다면, 이전에 5번 풍선을 터뜨린 화살이 있다고 한다면 해당 화살이 자동적으로 높이 4인 풍선을 맞출 것이기 때문에 화살을 다시 쏠 필요가 없다. 그렇기 때문에 입력으로 받은 풍선의 높이보다 1 높은 풍선을 맞췄던 화살이 있었는지 갯수를 체크해주면 된다.

#include <iostream>

using namespace std;

int Check[1000002] = {};

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

    int N;
    cin >> N;

    int Cnt = 0;

    for (int i = 0; i < N; ++i)
    {
        int H;
        cin >> H;

        ++Check[H];
        
        if (Check[H + 1] > 0)
        {
            --Check[H + 1];
        }

        else
        {
            ++Cnt;
        }

    }

    cout << Cnt;
}