[C++][백준 30892] 상어 키우기

문제

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

접근 방법

아기 상어의 몸집보다 작은 상어들 중에서 가장 몸집이 큰 상어가 무엇인지 항상 알 수 있게 해주면 됩니다.

코드

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
using ll = long long;

int N, K;
ll T;
int A[200000];
priority_queue<int> pq;

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N >> K >> T;

    for (int i = 0; i < N; ++i)
    {
        cin >> A[i];
    }

    sort(A, A + N);

    int index = 0;

    while (K--)
    {
        while (index < N && A[index] < T)
        {
            pq.push(A[index]);
            ++index;
        }

        if (pq.empty())
        {
            break;
        }

        T += pq.top();
        pq.pop();
    }

    cout << T;
    return 0;
}

풀이

정렬을 한 뒤 아기 상어의 몸집보다 작은 상어들의 몸집을 우선순위 큐에 넣어주면 됩니다.
그렇게 하면 우선순위 큐에 가장 위에 있는 값이 아기 상어의 몸집보다 작으면서 가장 큰 몸집이게 됩니다.