[2109] 순회강연

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

2109번: 순회강연

<문제>

i일에 진행되는 강연을 갈지를 판별해야 한다고 보면, [1, i]일에 진행되는 모든 강연을 큐에 넣는다.

큐의 size()가 i보다 크다면, size를 i로 맞추기 위해서 가장 싼 강연부터 빼준다.

로직은 매우 간단하고 직관적인데 구현방식에 대한 고민이 필요하다. 

2중 loop로 구현하면 간단하겠지만, 그 경우 강연 선택 여부에대한 bool []이 추가적으로 필요할 수 있겠다.

입력받은걸 하나씩 넣는다면, 큐의 size()가 i+1 이하에 있으므로 while이 아닌 if로 구현이 가능하다.

 

<소스코드>

#include <bits/stdc++.h>

using namespace std;

using pi = pair<int, int>;

int n, ans;

vector<pi> v;

priority_queue<int, vector<int>, greater<int>> q;

int main(void) {

    ios_base::sync_with_stdio(0);

    cin.tie(0);

    cin >> n;

    v.resize(n);

    int i;

    for (i = 0; i < n; i++) cin >> v[i].second >> v[i].first;

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

    for (i = 0; i < n; i++) ans += v[i].second;

    for (i = 0; i < n; i++) {

        q.push(v[i].second);

        if (q.size() > v[i].first) {

            ans -= q.top();

            q.pop();

        }

    }

    cout << ans;

    return 0;

}