1781번: 컵라면
상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라
www.acmicpc.net
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
struct Question{
int deadline; int cup;
bool operator< (Question question) const{ //오름차순
if(deadline==question.deadline)
return cup<question.cup;
return deadline<question.deadline;
}
};
int main(){
int n;
scanf("%d", &n);
vector<Question> v;
for(int i=0; i<n; i++){
int a,b;
scanf("%d %d", &a,&b);
v.push_back({a,b});
}
sort(v.begin(), v.end()); //오름차순 정렬 (deadline기준)
priority_queue<int> pq; //선택한 문제의 컵라면 저장
for(int i=0; i<v.size(); i++){
if(pq.size()<v[i].deadline) //데드라인이 아직 안됐으면
pq.push((-1)*v[i].cup);
else{
//데드라인이 지났지만, 기존에 선택한 문제보다 더 많은 컵라면을 얻을 수 있는 경우
if(!pq.empty() && pq.top()*(-1)<v[i].cup){
pq.pop();
pq.push((-1)*v[i].cup);
}
}
}
int ans = 0;
while(!pq.empty()){
ans += (-1)*pq.top();
pq.pop();
}
printf("%d", ans);
return 0;
}
** 그리디 문제
" 현 위치에서 최적인 경우를 선택한다. "
즉, 계속해서 최적의 경우를 선택하며 갱신해나감!
데드라인을 기준으로, 더 많은 컵라면을 받을 수 있는 문제를 선택해야 한다.
=> 더 많은 컵라면을 받기 위해서는, ①데드라인 ②컵라면개수 를 따져야 함!!
① 데드라인
deadline을 기준으로 오름차순 정렬한다.
모든 문제를 선택할 지/선택하지 않을지 를 확인해야하므로, 컵라면의 개수(cup)도 함께 오름차순 정렬한다.
② 컵라면 개수
현재까지 선택한 컵라면을 저장하기 위해, 우선순위큐를 이용한다.
왜 우선순위큐를 이용했냐면 - 선택한 컵라면을 오름차순으로 저장하려고!
큐는 처음 size가 0이기 때문에, 현재의 시간으로 볼 수 있다. 따라서, 큐.size()와 deadline을 비교한다.
1) 큐.size()가 deadline보다 작다면 == 아직 deadline이 되지 않았으므로, 해당 문제를 푼다. (해당 컵라면을 저장) : push
2) 큐.size()가 deadline보다 크다면 == deadline이 지난 경우
더 뒤의 deadline을 선택했을 때, 더 많은 컵라면을 받을 수 있는지를 확인한다.
즉, '지금까지 선택된 컵라면 中 가장 적은 컵라면의 수' 는 큐.top()을 의미하므로(오름차순 정렬)
선택된 문제 중 가장 적은 컵라면 수를 수정하여, 최적의 경우를 갱신해나간다. : pop&push
'1d-1c > BOJ' 카테고리의 다른 글
1149_RGB거리 (C++) (0) | 2020.12.29 |
---|---|
1260_DFS와 BFS (C++) (0) | 2020.12.22 |
1932_정수 삼각형 (JAVA) (0) | 2020.12.18 |
14889_스타트와 링크 (JAVA) (0) | 2020.12.15 |
10814_나이순 정렬 (JAVA) (0) | 2020.12.05 |