2109번: 순회강연 [C++]

순회강연 

다국어

한국어   

시간 제한         메모리 제한         제출         정답         맞힌 사람         정답 비율

2 초

128 MB

9579

3628

2738

37.456%

문제

한 저명한 학자에게 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값이 주어진다.

 

출력

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

예제 입력 1 복사

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

예제 출력 1 복사

185

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

흐름

코드

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

int n,d,p,ret;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //1. 입력받기
    cin >>n;
    pair<int,int> l[n];
    for(int i=0;i<n;i++){
        cin >> l[i].second >> l[i].first; //first:강연기간, second:강연료
    }
    sort(l, l+n, greater<>()); //강연기간으로 내림차순 정렬
    //2. 가능한 강연들 모두 저장하여 일자마다 가능한 고비용 강의 하나씩 pop
    int maxday=l[0].first;
    priority_queue<int> pq;
    int j=0;
    for(int i=maxday;i>=1;i--){ //큰 날짜부터 작은 날짜까지 
        while(j<n && i<=l[j].first) pq.push(l[j++].second); //가능한 강의 다 집어넣기
        if(pq.size()){
            ret += pq.top(); pq.pop();
        }
    }//3. 정답 출력
    cout << ret;

}

 

그리디

sort 또는 pq(우선순위 큐) : 둘 다 사용할 수도 있음

 

최대

가능한 값의 최소를 작게 만들거나 최대를 크게 만드는 것

 

경우의 수 4가지

day를 오름차순, 내림차순

pq를 오름차순, 내림차순

 

선생님 코드 흐름 

작은 날짜부터 큰 날짜까지 진행하면서 비용 작은것을 pop해주었다.

기간 1일 강연을 pop해주고 기간 2일 강연을 2개 남겨두더라도 2일 강연은 1일,2일 모두 수행 가능하기때문이다.

 

선생님 코드

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

int n, ret;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //1. 입력하기
    cin >> n;
    pair<int,int> a[n];
    for(int i=0;i<n;i++)
        cin >> a[i].second >> a[i].first; //pair: 강연날짜-비용
    sort(a, a+n);
    //2.  날짜별로 고비용 강의 정하기
    priority_queue<int, vector<int>, greater<int>> pq;
    for(int i=0;i<n;i++){
        pq.push(a[i].second);
        if(pq.size()>a[i].first) pq.pop();
    }
    //3. 총 강의 비용 출력하기
    while(!pq.empty()){
        ret += pq.top(); pq.pop();
    }
    //4. 출력하기
    cout << ret;

}