[백준] 컵라면

그리디한 문제는 계속 풀어도 아직도 아리송 한거같다. 분명히 태그에는 우선순위큐라고 써있었지만 뭔가 푸는데 이거 꼭 우선순위 큐를 사용해야하는 생각밖에 안들고 그냥 정렬로도 할 수 있지 않나 생각하다가도 제출하면은 계속 틀린다.

아리송하지만 다른 사람들의 풀이 방법을 읽어보면서 조금씩 배우는 중이다. 이 기분은 마치 그래프 탐색을 처음 배웠을때같은 기분이라 좀 신기하다. 최근에는 그래프 탐색은 많이 안하고 있는데 이것도 어느순간이면 실력이 늘 수 있을거라고 생각한다.

패턴을 잘 생각해야 한다는 느낌을 받았다. 항상 최선의 선택만을 해야하는 그리디 문제에서 최소/최대 답을 묻는다면 최대 혹은 최소의 선택을 강요하는 초이스를 생각해야 하고 이 문제에서는 최대 컵라면을 가져와야했다. 앞에 있는 숫자는 시간의 개념인데 1시간이 늘어나고 같은 데드라인에서 문제를 풀때는 선택이 필요하다, 즉 같은 데드라인을 가진 문제를 풀때는 더 컵라면을 많이 주는 쪽을 선택해야하는게 그리디한 알고리즘이란것.

당연히 데드라인이 적은 숫자부터 푸는게 맞기때문에 시간순 오름차순으로 정렬 해주고 pq.size() 를 현시간 개념으로 기준 잡아 계속 큐에 넣어주었다. 만약 같은 데드라인안에 여러 문제를 풀어야 하는 경우면 컵라면이 높은 순서로 넣어주었고 같은 데드라인안에 여러 문제를 풀더라도 첫번째 혹은 그 전에 풀었던 문제를 버리는 선택도 필요했다.

#include <iostream> 
#include <bits/stdc++.h> 
#define endl "\n"
#define MAX 100010
using namespace std;

int N; 
vector<pair<int,int>> problems; 

void Input(){
    cin >> N; 
    for(int i = 0; i < N; i++){
        int a, b; 
        cin >> a >> b; 
        problems.push_back({a,b}); 
    }
}

void Solution(){
    sort(problems.begin(),problems.end()); 
    priority_queue<int,vector<int>,greater<int>> pq; 
    for(int i = 0; i < N; i++){
        if(pq.size() < problems[i].first) pq.push(problems[i].second); 
        else{
            if(pq.top() < problems[i].second){
                pq.pop(); 
                pq.push(problems[i].second);
            }
        }
    }
    int sum = 0; 
    while(!pq.empty()){
        sum += pq.top();
        pq.pop(); 
    }
    cout << sum; 
}


void Solve(){
    Input();
    Solution(); 
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen("input.txt", "r", stdin);
    Solve();
    return 0;

}

배운점:
1. 그리디 알고리즘 최적화
2. 아이디어 생성