[Gold II] 컵라면 - 1781
성능 요약
메모리: 76172 KB, 시간: 868 ms
분류
자료 구조, 그리디 알고리즘, 우선순위 큐
제출 일자
2023년 10월 23일 12:40:35
문제 설명
상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라인을 정하였다.
문제 번호 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|
데드라인 | 1 | 1 | 3 | 3 | 2 | 2 | 6 |
컵라면 수 | 6 | 7 | 2 | 1 | 4 | 5 | 1 |
위와 같은 상황에서 동호가 2, 6, 3, 1, 7, 5, 4 순으로 숙제를 한다면 2, 6, 3, 7번 문제를 시간 내에 풀어 총 15개의 컵라면을 받을 수 있다.
문제는 동호가 받을 수 있는 최대 컵라면 수를 구하는 것이다. 위의 예에서는 15가 최대이다.
문제를 푸는데는 단위 시간 1이 걸리며, 각 문제의 데드라인은 N이하의 자연수이다. 또, 각 문제를 풀 때 받을 수 있는 컵라면 수와 최대로 받을 수 있는 컵라면 수는 모두 231보다 작거나 같은 자연수이다.
입력
첫 줄에 숙제의 개수 N (1 ≤ N ≤ 200,000)이 들어온다. 다음 줄부터 N+1번째 줄까지 i+1번째 줄에 i번째 문제에 대한 데드라인과 풀면 받을 수 있는 컵라면 수가 공백으로 구분되어 입력된다.
출력
첫 줄에 동호가 받을 수 있는 최대 컵라면 수를 출력한다.
풀이 방식
1. 문제는 데드라인으로 오름차순 정렬하고 라면으로 내림차순 정렬을 해주어야한다.
2. 알아두어야 할 점으로는 시간 1 순서일 때 데드라인 1인 걸 하는게 아니라 다른 걸 해도 됨
ex)
1 10
2 50
3 100
3 100
-> 10 + 50 + 100 이 아니라 50 + 100 + 100을 선택 할 수 있음
3. 그래서 데드라인을 기준으로 하는 것이 아니라 라면을 기준으로 보고 해야한다.
import java.io.*;
import java.util.*;
class Main
{
static class Problem implements Comparable{
int deadline;
int ramen;
public Problem(int deadline, int ramen) {
this.deadline = deadline;
this.ramen = ramen;
}
@Override
public int compareTo(Object o) {
Problem p = (Problem) o;
if(this.deadline != p.deadline){
return this.deadline - p.deadline;
}
return p.ramen - this.ramen;
}
}
public static void main(String args[]) throws IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
ArrayList<Problem> list = new ArrayList<>();
PriorityQueue<Integer> pq = new PriorityQueue<>();
StringTokenizer st;
int n = Integer.parseInt(br.readLine());
for(int i = 0; i < n; i++){
st = new StringTokenizer(br.readLine());
int deadline = Integer.parseInt(st.nextToken());
int ramen = Integer.parseInt(st.nextToken());
list.add(new Problem(deadline, ramen));
}
Collections.sort(list);
// list에서 데드라인이 낮은 순서로 빼와서 라면을 넣어준다.
for(Problem p : list){
int dead = p.deadline;
int ramen = p.ramen;
pq.offer(ramen);
// pq의 사이즈는 여태까지 흘러간 시간
// 만약 데드라인이 pq.size()보다 크다면 라면의 수가 가장 낮은 문제의 라면을 poll
if(dead < pq.size()){
pq.poll();
}
}
int result = 0;
while(!pq.isEmpty()){
result += pq.poll();
}
System.out.println(result);
}
}
'알고리즘 - Baekjoon > Gold' 카테고리의 다른 글
[백준] 7576번 : 토마토 Gold5(골드 5) - JAVA[자바] (0) | 2023.10.26 |
---|---|
[백준] 16987번 : 계란으로 계란치기 Gold5(골드5) - JAVA[자바] (1) | 2023.10.24 |
[백준] 1655번 : 가운데를 말해요 Gold 2(골드 2) - JAVA[자바] (1) | 2023.10.23 |
[백준] 13975번 : 파일 합치기3 Gold4(골드 4) - JAVA[자바] (1) | 2023.10.23 |
[백준] 1715번 : 카드 정렬하기 Gold 4(골드5) - JAVA[자바] (1) | 2023.10.23 |