[BOJ/Gold 5] 백준 27896 특별한 서빙(C++)

문제 링크

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

27896번: 특별한 서빙

 

문제

???: 가지라니, 비슷하지도 않잖아요...

NLCS Jeju에서는 파묻튀(파마산을 묻혀 튀긴 소고기)를 서빙하는 것을 좋아한다.

그러나, 학생들은 파묻튀보다는 신선한 가지를 먹고 싶어한다!

급식실에 N명의 학생들이 차례로 서 있다. 줄의 앞에서부터 i번째 학생이 가지 대신 파묻튀를 받았을 경우 xi만큼 불만도가 늘어나고, 가지를 받았을 경우에는 xi만큼 불만도가 내려간다. 단, 불만도의 초깃값은 0이다.

음식을 앞에 서있는 학생부터 순서대로 서빙할 때, 어떤 한 순간이라도 불만도가 M 이상이 되면 학생들은 ‘가지 운동’을 일으키게 된다.

가지 운동을 일으키지 않게 하기 위한 가지의 최소 개수를 구하는 프로그램을 작성하시오.

 

입력

첫 번째 줄에 N과 M이 공백으로 구분되어 주어진다.

두 번째 줄에 xi를 나타내는 N개의 정수가 공백으로 구분되어 주어진다.

 

출력

첫 번째 줄에 학생들이 가지 운동을 일으키지 않게 하기 위한 가지의 최소 개수를 출력한다.

 

제한

•  1 ≤ N ≤ 200,000
•  1 ≤ M ≤ 10^9
•  0 ≤ xi ≤ 10^9

 

예제 입력 1

5 3
0 0 2 0 2

예제 출력 1

1

예제 입력 2

10 90
14 6 12 16 14 6 20 19 16 12

예제 출력 2

2

 

 

알고리즘 분류

• 그리디 알고리즘
• 자료 구조

 

풀이

첫 번째 학생부터 계속 파묻튀를 먹이면서 불만도의 총합을 xi만큼 증가시킨다.

그러다가 불만도가 M 이상이 되면, 지금까지 파묻튀를 먹인 학생들 중에서 불만도가 큰 순서대로 파묻튀 대신 가지를 먹이고 불만도의 총합에서 해당 학생의 x를 2번 뺀다. 이것을 불만도가 M 미만이 될 때까지 반복한다.

마지막으로 가지의 개수를 출력한다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#define LL long long
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N;
LL M, I, Sum;
priority_queue<LL> PQ;
int Answer;

void input() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        cin >> I;
        PQ.push(I);
        Sum += I;
        while (Sum >= M) {
            Answer++;
            Sum -= (PQ.top() * 2);
            PQ.pop();
        };
    }
}

void find_Answer() {
    cout << Answer << "\n";
}

int main() {
    FASTIO
    input();
    find_Answer();

    return 0;
}