백준 2109 순회 강연 ( greedy )

문제 : 2109번: 순회강연 (acmicpc.net)

2109번: 순회강연

 

접근과정

이 문제를 풀기 위해서, 정렬된 vector와 priority queue 2가지를 사용했습니다.

 

처음에는 그냥 vector만을 사용해서 해당 날짜마다 가장 큰 강연료들만 더해주면 된다고 생각했는데,

문제에서 d일 안에 와서 강연을 해준다고 했지, d일에만 정확히 강연을 한다고는 하지 않았습니다.

 

예를들어 (d,p) = (1,1), (2,10), (2,10) 예제의 경우 날짜마다 가장 큰 강연료를 더해주면 11이 나오지만,

2일 안에 10짜리 강연료 2개를 할 수도 있기 때문에 답은 20이 나와야 합니다.

 

풀이과정

1. vector에 d,p 값들을 넣고 정렬을 해주는데

먼저 d에 대해 오름차순 정렬을 하고 d값이 같다면 p에 대해 오름차순이 되어야 합니다.

 

2. priority_queue 또한 오름차순 정렬이 되도록 생성합니다.

for문을 순회하면서 강연료를 하나씩 넣어주고 answer에도 누적해서 더해주는데,

만약 pq의 크기가 앞서 더했던 강연료의 기간보다 더 크다면, pq의 첫번째 값만큼을 빼주도록 합니다.

 

(d,p) = (1,1), (2,10), (2,10) 이 예제를 다시 살펴보면,

1. 첫 번째, 두 번째 값까지는 pq에 넣어주게 되고, 

2. 세 번째 값인 10을 넣었을 경우 해당 d 값보다 pq의 크기가 더 크기 때문에

pq의 top ( 가장 작은 값 ) 만큼을 빼주게 되며 답이 구해지게 됩니다.

 

 

#include <iostream>
#include <vector>
#include <stdio.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
int N;
int p,d;
typedef struct option {
    int range, money;
}op;
vector < op > v;
priority_queue < int , vector < int >, greater < int > > pq;

bool cmp(const op &a, const op &b) {
    if(a.range < b.range) return true;
    else if(a.range == b.range) {
        if(a.money < b.money) return true;
    }
    return false;
}

int solution() {
    int ans = 0;
    for(int i=0; i<N; i++) {
        pq.push(v[i].money);
        ans += v[i].money;

        if(pq.size() > v[i].range) {
            ans -= pq.top();
            pq.pop();
        }
    }
    return ans;
}

int main()
{
    scanf("%d",&N);
    for(int i=0; i<N; i++) {
        scanf("%d %d",&p,&d);
        v.push_back({d,p});
    }
    sort(v.begin(),v.end(),cmp);
    printf("%d\n",solution());
}