[그리디 / BOJ 2109 / C++] 순회강연

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

2109번: 순회강연

 

1) <D,P> 를 저장할 vector<pair<int,int>>를 만들고, sorting 한다.
2) 해당 <D,P>를 최소힙을 통해 res를 구한다.

전형적인 우선순위 큐를 활용한 그리디 문제. 이 문제로 연습을 하면 대충 감이 잡힐 것 같다.

 

감을 익히자!!

 

일단 도저히 못풀겠어서 여기저기 답안 참고하며 풀어갔다.

 

우선 문제를 꼼꼼히 확인안한 나의 첫번째 논리는 

 

"엥? 이거 그냥 날짜순으로 정렬하고 각 날짜에서 최대값 구해서 다 더하면 되지 않나?"

 

하고 좀 고민하다가 1만짜리 배열을 만들어서 v[D] = max(P, ~) 이런식으로 풀었다.

 

테케도 다 통과했겠다 바로 넣었더니

 

바로 3% 틀렸습니다 .. ㅎㅎ

 

문제 다시 읽어보자~

 

D일 "이내"이다. 즉, D일이 아니라 D일 이내면 언제든지 강의를 할 수 있다는 뜻이다.

만약 2일이내가 100, 99 이렇게 2개 있고, 1일이내가 1, 2 이렇게 2개 있다면,

 

1일차에 100짜리, 2일차에 99짜리를 하는 것이 합당할 것이다.

 

그렇다면 새롭게 생각하자. 우선 (D, P)를 sorting 한다. 그러면 날짜(D)를 기준으로 오름차순 정렬되고, 같은 경우 P를 기준으로 정렬된다.

 

그리고 1일차에 진행할 강연, 2일차에 진행할 강연 ... 이렇게 하나씩 선택해나가면 된다. 이를 최소힙으로 구현한다.

히스토그램을 이런 느낌이다. 먼저 1일 이내에 해당하는 것을 모두 힙에 넣어주고, 가장 큰 P가 되는 경우를 남기고 모두 Pop을 한다. 2일차로 넘어가면, 같은 방식으로 모두 힙에 넣어주고, 2개만 남기고 모두 pop한다. 3일차가 되면, 모두 힙에 넣고, 3개만 남기고 모두 pop한다.

 

이를 N까지 진행하면 된다.

 

나머진 코드를 보면서 생각하자.

 

 

#include <bits/stdc++.h>

using namespace std;

int n, a, b, ret;

vector<pair<int, int>> v;
priority_queue<int, vector<int>, greater<int>> pq; // 최소힙

int main(){
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> a >> b; v.push_back({b, a});
    }
    
    sort(v.begin(), v.end()); // day 순으로 정렬. 오름차순.
    
    
    for(int i = 0; i < n; i++){ // 0부터 오름차순으로 올라감.
        pq.push(v[i].second); // 해당 날짜에 맞는 가격 넣기.
        if(pq.size() > v[i].first){ // pq.size()가 해당날짜보다 크면 pop 해주기. ex) 1일 10, 1일 20, 1일 30 (size > 해당day) 이렇게 되면 최소힙이므로 1일 30만 남게됨.
            pq.pop(); // 가장 낮은 최소 가격이 pop됨.
        }
    }
    
    
    while(pq.size()){
        ret += pq.top(); pq.pop(); // 힙에 남은 모든 가격을 합하면 답!
    }
    
    cout << ret << "\n";
}