백준 2109 순회강연 | C++

 

 

이번 포스팅은 백준 2109번 순회강연입니다.

아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다.

www.acmicpc.net/problem/2109

2109번: 순회강연

 

 

기본 알고리즘

우선순위 큐 priority queue

 

풀이

한 대학의 강연은 한 번만 간다.

 

입력

p  |   20  2   10   100   8      5     50

d  |     1   1     3        2   2    20     10

 

입력 값을 pair로 묶어 벡터에 저장 후 d를 기준으로 오름차순 정렬

{1, 10}

{1, 20}

{2, 8}

{2, 100}

{3, 10}

{10, 50}

{20, 5}

 

우선순위 큐에 v[i].second (=p)를 저장하면 루트에 최소 p가 유지된다.

 

v[i].second (=p) 를 합계에 저장한다.

 

만약 큐의 크기보다 v[i].first (=d)의 크기가 크면   (= 같은 기한을 둔 강연이 2개 이상의 대학에 있음)

큐의 루트인 최솟값 제거, 합계에서도 뺀다.

 

합계 출력

 

예제)

i=0

v[0] =  {1,10}

pq = {10},  result = 10

 

i=1

v[1] =  {1,20}

pq = {10, 20},  result = 30

★pq.size() > v[i].first

           2                    1

최솟값 제거, result 차감

pq = {20}, result = 20

 

i=2

v[2] =  {2, 8}

pq = {8, 20},  result = 28

 

i=3

v[3] =  {2, 100}

pq = {8, 20, 100},  result = 128

★pq.size() > v[i].first

            3                     2

최솟값 제거, result 차감

pq = {20, 100}, result = 120

 

...(같은 방식으로 진행)

 

 

전체 코드

 

//백준2109 순회강연
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
 
int n;
priority_queue<int, vector<int>, greater<int>> pq; //최솟값이 루트로 가는 우선순위큐
vector<pair<int, int>> v; //d, p 저장 벡터
int result; // 출력
 
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int p, d;
        cin >> p >> d;
        v.push_back(make_pair(d, p)); //day 순으로 정렬하기 위해 d, p로 저장
    }
 
    sort(v.begin(), v.end());
 
    for (int i = 0; i < n; i++) {
        pq.push(v[i].second);
        result += v[i].second;
 
        if (pq.size() > v[i].first) {
            result -= pq.top();
            pq.pop();
        }
    }
    
    cout << result;
 
    return 0;
}