[백준 27896] 특별한 서빙

🔗알고리즘 문제

지금까지 골드 문제란 것에 대해서 조금 겁을 먹고 있었는데 이제 슬슬 도전해봐야겠다고 생각이 들어 풀게 된 문제이다. 평소 좋아하고 자주 사용하던 자료구조인 우선순위 큐를 이용하는 문제여서 생각보다 손 쉽게 풀 수 있었다.

문제 분석

이 문제는 폭동을 막기 위한 최소 가지의 갯수를 구하는 문제이다.

손님들이 파묻튀를 받았을 때는 a만큼 불만도가 올라가게 되고, 가지를 받았을 경우에는 불만도가 a만큼 줄어들게 된다.
불만도가 m보다 높아질 경우에는 참다 못한 손님들이 폭동을 일으킨다고 한다....

발상

손님들에게 파묻튀를 먹이면서 불만도를 측정하다가 불만도가 m을 넘어가면 현재까지 가장 불만도가 높은 손님에게 가지를 주는 것이 가장 효율적이다.

이를 위해선 우선순위 큐를 사용하는 것이 가장 효율적이다.

알고리즘 설계

1. 손님들의 불만도를 우선순위 큐에 저장한다.
2. 불만도를 측정하다 불만도가 m보다 높아질 경우 우선순위 큐에 가장 큰 불만도를 제거하고 가지 수를 카운트한다.
3. 최종 가지 수를 출력한다.

코드

#include<iostream>
#include<queue>

using namespace std;

int main(){
    priority_queue<int> nums;

    int n;
    int m;

    int answer = 0;
    int temp = 0;

    cin >> n >> m;

    for(int i = 0; i < n; i++){
        int input;
        cin >> input;
        nums.push(input);
        temp += input;

        while(temp >= m){
            ++answer;
            temp -= nums.top() * 2;
            nums.pop();
        }
    }

    cout << answer;
}