그리디한 문제는 계속 풀어도 아직도 아리송 한거같다. 분명히 태그에는 우선순위큐라고 써있었지만 뭔가 푸는데 이거 꼭 우선순위 큐를 사용해야하는 생각밖에 안들고 그냥 정렬로도 할 수 있지 않나 생각하다가도 제출하면은 계속 틀린다.
아리송하지만 다른 사람들의 풀이 방법을 읽어보면서 조금씩 배우는 중이다. 이 기분은 마치 그래프 탐색을 처음 배웠을때같은 기분이라 좀 신기하다. 최근에는 그래프 탐색은 많이 안하고 있는데 이것도 어느순간이면 실력이 늘 수 있을거라고 생각한다.
패턴을 잘 생각해야 한다는 느낌을 받았다. 항상 최선의 선택만을 해야하는 그리디 문제에서 최소/최대 답을 묻는다면 최대 혹은 최소의 선택을 강요하는 초이스를 생각해야 하고 이 문제에서는 최대 컵라면을 가져와야했다. 앞에 있는 숫자는 시간의 개념인데 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. 아이디어 생성