[백준 2109] 순회강연

문제유형 :

그리디

복기 :

최초 풀이 당시 order by day, price로 정렬 후 각 day 마다 최대값을 뽑아냄. 하지만 day가 같더라도, 최대 price를 가지는 값들을 골라야 했음(반례 생각 x).

fail ver :

#include <bits/stdc++.h>
using namespace std; 
typedef pair<int,int> pp; 
typedef map<int,int> m;
void l(){ cout << " ------- " << endl;}

int n; 
vector<pp> v; 

//customSsort : order by date , price
bool cSort(const pp &a, const pp &b){
    if(a.second != b.second){//sort by day 
        return a.second < b.second; 
    }
    //sort by money
    return a.first > b.first; 
}

//input 
void i(){
    cin >> n; 
    int d,p; 
    for(int i=0; i<n; i++){
        cin >> d;
        cin >> p; 
        v.push_back({d,p});
    }
}

//solution 
void s(){
    int money=0, date=0;
    sort(v.begin(), v.end(), cSort ); 
    for(pp dp : v){
        if(date < dp.second){ 
            money += dp.first; 
            date = dp.second;//현재 날짜짜
        }
    }
    cout << money;
}

void sol(){
    i();s(); 
}

int main() {
    sol(); 
    return 0;
}
     

success ver :

priority queue를 사용해서 풀 수 있다.

1. 각 day마다, 각 대학의 pay를 pq(오름차순)에 넣어준다.
2. 해당 day보다 pq의 크기가 커지는 경우(하루 당 방문 횟수가 한 번인데 가능한 방문 횟수보다 커지는 경우)
3. pop해서 최소값을 내보낸다.

아래의 pq를 사용했다.

priority_queue<int, vector<int> ,greater<int>> pq 

1. int 값을 담고
2. underlying 자료구조는 vector이며
3. 오름차순으로 (greater)로

pq를 생성한다.

#include <bits/stdc++.h>
using namespace std; 
typedef pair<int,int> pp; 
typedef map<int,int> m;
priority_queue<int, vector<int>,greater<int>> pq; 
void l(){ cout << "------- " << endl;}
int n; vector<pp> v; 

// day 정렬 
bool cSort(const pp &a, const pp &b){
    if(a.second != b.second){//sort by day 
        return a.first < b.first; 
    }
    return a.second > b.second; //sort by money 
}

//input 
void i(){
    cin >> n; 
    int d,p; 
    for(int i=0; i<n; i++){
        cin >> p;
        cin >> d; 
        v.push_back({d,p});
    }
    sort( v.begin(), v.end() ); 
}

//solution 
void s(){
    int money=0;
    for(pp dp : v){
        pq.push(dp.second);//price 
        if(pq.size() > dp.first) pq.pop();// pop 
    }
    while(!pq.empty()){
        money += pq.top(); pq.pop();         
    }
    cout << money;
}

void sol(){
    i();s(); 
}

int main() {
    sol(); 
    return 0;
}
     

쉬운 문제 같았는데 오래 걸렸다. 샷건 마렵다.
중간에 또 cSort 때문에 문제가 있었는데, 이 부분 다시 확인 해봐야 겠다.