[백준 2109] 순회강연

이 문제를 [백준 1202] 보석도둑에서의 lower_bound를 이용한 풀이와 비슷하게 시도해보고자 한다.

lower\_bound(x): x이상의 수 중 최솟값 인데

순회강연의 문제에서는 각 강연의 endline이 주어지고, 그 endline안에만 강연을 할 수 있다.

즉 day=2일때, endlined이 2이하인 강연만 할 수 있어서 정확히 lower_bound의 정의에 반대이다.

---

여기서 중요한것이 정확히 lower_bound의 반대라는 점인데,

그렇다면 각 케이스에서 가장 큰 endline을 maxEndline이라고 했을 때,

endline = maxEndline - endline;

이 상태에서는 "lower_bound(x'): x'이하의 수중 최댓값"이 된다.

따라서, day=2일때, lower_bound(day)의 결과는 endline이 2 이하인 강연 중 비용이 가장 큰 것의 index가 나오게 된다.

---

이 풀이는 뭔가 머릿속으로는 이해가 되는데, 말로 하려니깐 정의자체가 어려운것같다.

#include <bits/stdc++>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pair<int, int> > vpii;

// INT_MAX = 2^31 ~= 2.1e9
// LLONG_MAX = 2^63 ~= 9.2e18

const int MAX=(int)1e4;
pii lecture[MAX+5]; // <비용, 기간>
multiset<int> day;

int main(){
  int n;
  scanf("%d", &n);

  int nDay=0;
  for(int i=0; i<n; i++){
    scanf("%d %d", &lecture[i].first, &lecture[i].second);
    if(lecture[i].second>nDay) nDay=lecture[i].second;
  }
  for(int i=0; i<n; i++){
    lecture[i].second=nDay-lecture[i].second;
  }
  for(int i=0; i<nDay; i++) day.insert(i);

  sort(lecture, lecture+n, greater<pii>()); // 비용이 큰 순으로 정렬을 한다.

  ll answer=0;
  for(int i=0; i<n; i++){ // i는 강연의 순번, 비용이 높은것이 먼저 나온다.
    auto iter=day.lower_bound(lecture[i].second);
    if(iter!=day.end()){
      // 값을 찾았다면 비용을 더해주고, 해당 날은 제거한다.
      answer+=lecture[i].first;
      day.erase(iter);
    }
  }
  printf("%lld", answer);
  return 0;
}