Pr.2109 순회강연

Pr.2109 순회강연

문제

한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. 각 대학에서 제시하는 d와 p값은 서로 다를 수도 있다. 이 학자는 이를 바탕으로, 가장 많은 돈을 벌 수 있도록 순회강연을 하려 한다. 강연의 특성상, 이 학자는 하루에 최대 한 곳에서만 강연을 할 수 있다.

예를 들어 네 대학에서 제시한 p값이 각각 50, 10, 20, 30이고, d값이 차례로 2, 1, 2, 1 이라고 하자. 이럴 때에는 첫째 날에 4번 대학에서 강연을 하고, 둘째 날에 1번 대학에서 강연을 하면 80만큼의 돈을 벌 수 있다.

입력

첫째 줄에 정수 n이 주어진다. 다음 n개의 줄에는 각 대학에서 제시한 p값과 d값이 주어진다.

출력

첫째 줄에 최대로 벌 수 있는 돈을 출력한다.

예제 입력

7
20 1
2 1
10 3
100 2
8 2
5 20
50 10

예제 출력

185

풀이과정

전제조건

1. 시간 복잡도, 공간 복잡도
   • 시간복잡도 : n개의 대학 수 만큼 매번 순회 N^2 100,000,000 시간 초과 -> 단순 비교 불가
2. 최대, 최소 조건
   • n의 길이 : 10,000
3. 사용 알고리즘
   • 날짜를 기준으로 정렬
   • 우선순위큐의 성질을 이용해서 강의를 넣을 수 있다.
   • 큐의 사이즈와 큐에 삽입한 강의 날짜를 비교
   • 큐 사이즈 > 날짜 : 날짜 초과하는 강의 빼기
   • 큐 사이즈 < 날짜 : 그냥 넣기
4. 반례, 경계값

제출 코드

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

int n, p, d, res;
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 >> p >> d;
        v.push_back({d, p});
    }

    sort(v.begin(), v.end());

    for (int i = 0; i < n; i++){
        pq.push(v[i].second);
        if (pq.size() > v[i].first){
            pq.pop();
        }
    }

    while(pq.size()){ 
        res += pq.top();
        pq.pop();
    }

    cout << res << '\n';
    return 0;
}

해설

생각해볼 점

• 우선순위 큐의 성질:

  우선순위 큐에 top에는 항상 최소값 or 최대값이 위치한다. </br> 그리디에서는 순간의 선택이 최적의 선택이 되어야하는데 우선순위 큐의 성질을 이용하면 top은 최악의 선택을 위치 시킬 수 있다.</br> 최악의 선택을 배재 하고 다음 선택을 진행 하면 이전 선택들은 최선의 선택들만 남는다 </br>

정답 코드

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

typedef long long ll;
int a[1004];
vector<pair<int,int>> v;
map<int,int> mp, mp_first;

bool cmp(pair<int,int> a, pair<int, int> b){
  if(a.first == b.first){
    return mp_first[a.second] < mp_first[b.second];
  }
  return a.first > b.first;
}


int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int n,c;
  cin >> n >> c;
  for (int i =0; i < n; i++){
    cin >> a[i];
    mp[a[i]]++;
    if(mp_first[a[i]] == 0) mp_first[a[i]] = i + 1;
  }

  for(auto it :mp){
    v.push_back({it.second, it.first});
  }

  sort(v.begin(), v.end(), cmp);

	for(auto i : v){
		for(int j = 0; j < i.first; j++){
			cout << i.second << " ";
		}
	} 

  
  return 0;
}