[ 백준 27896 ] 특별한 서빙 (c/c++)

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

 

 

[ 문제 요약 ]

파마산을 묻혀 튀긴 소고기를 받을 경우 학생들의 불만도가 올라가고 가지를 받을 경우 불만도가 낮아질 때 학생들의 불만도가 M이상이 되지 않도록 하기 위한 가지의 최소 개수를 출력한다.

 

 

[ 문제 풀이 ]

1. 학생들의 불만도를 입력받아 더했을 때 총합이 M보다 낮으면 그냥 더한 후 우선순위 큐에 넣는다.

2. 만약 M을 넘을 경우 우선순위 큐에서 가장 큰 값인 top 값을 총합이 M보다 작아 질 때까지 2를 곱해서 뺀다.

3. 빼는 횟수만큼 가지의 개수를 늘린다.

 

 

[ 소스 코드 ]

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

long long M, sum = 0, cont = 0;
int N;
priority_queue<long long> pq;

int main() {
    cin >> N >> M;
    for (int i=0; i<N; i++){
        long long a;
        cin >> a; pq.push(a);
        sum += a;
        while (sum >= M){
            cont++;
            sum -= pq.top() * 2;
            pq.pop();
        }
    }
    cout << cont;
    return 0;
}

 

 

[ 주의할 점 ]

학생들이 순서대로 줄을 서고 있는 것이기 때문에 정렬을 해서 풀는 것은 안된다.