75. 최대수입 스케쥴 [우선순위 큐 응용]

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다.

문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅

 

 

입력예제 1

6

50 2

20 1

40 2

60 3

30 3

30 1

 

출력예제 1

150

 

풀이 

- 남아있는 날짜가 많은 것 부터 스케쥴링 하는 것이 이 문제의 핵심

- money, when을 구조체로 만들어서 벡터에 넣어준 후 operator정렬기준에 따라 남아있는 날짜가 많은 순으로 정렬한다

(money는 정렬과 상관X)

 

정렬 전	정렬 후
50 2	60 3
20 1	30 3
40 2	50 2
60 3	40 2
30 3	20 1
30 1	30 1

- 3일 => 60과 30중 큰 수인 60을 res에 더함

- 2일 => 위에서 남은 30 / 2일자에 있는 50, 40 중 가장 큰 수인 50을 res에 더함

- 1일 => 위에서 남은 30, 40 / 1일자에 있는 20, 30 중 가장 큰 수인 40을 res에 더함

총 60+50+40 = 150을 출력한다

 

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
//75. 최대수입 스케쥴(priority_queue 응용)

struct Data{
    int money;
    int when;
    Data(int a, int b){
        money=a;
        when=b;
    }
    //정렬기준
    bool operator<(const Data &b)const{
        return when>b.when; //앞에게 큰값을 가진다 => 내림차순 정렬
    }
};

int main(){
    int n, i, j, a, b, res=0, max=-2147000000;
    vector<Data> T;
    priority_queue<int> pQ;
    scanf("%d", &n);
    for(i=1;i<=n;i++){
        scanf("%d %d", &a, &b);
        T.push_back(Data(a, b));
        if(b>max) max=b; //마지막 강연할 날짜 구함
    }
    sort(T.begin(), T.end()); //operator 기준에 따라 정렬
    j=0;
    for(i=max;i>=1;i--){
        for( ; j<n; j++){
            if(T[j].when<i) break;
            pQ.push(T[j].money); //날짜가 크거나 같은것만 push
        }
        if(!pQ.empty()){
            res+=pQ.top();
            pQ.pop();
        }
    }
    printf("%d\n", res);
    return 0;
}