문제 링크
문제
티어: 골드 2
알고리즘: 그리디, 우선순위 큐, 정렬
입력
첫 줄에 숙제의 개수 N (1 ≤ N ≤ 200,000)이 들어온다. 다음 줄부터 N+1번째 줄까지 i+1번째 줄에 i번째 문제에 대한 데드라인과 풀면 받을 수 있는 컵라면 수가 공백으로 구분되어 입력된다.
출력
첫 줄에 동호가 받을 수 있는 최대 컵라면 수를 출력한다.
풀이
구하고자 하는 것은 최대 컵라면 수다.
컵라면 수를 최대한 많이 받기 위해서는 최대한 데드라인에 맞춰서 풀어야 많은 문제를 풀 가능성이 높아진다는 것이다.
예를 들어 데드라인이 6인데 가장 먼저 풀면 데드라인 1인 문제를 풀지 못하게 돼서 최댓값과 멀어진다.
문제 예제를 가지고, 자세히 설명해 보겠다.
먼저, 1시간이 지났다고 생각해 보자
풀 수 있는 총 문제는 한 문제이다.
그러면 어떤 문제를 풀어야 할까? 일단 앞에서 말했듯이 데드라인을 최대한 맞추기 위해서 1인 문제들을 일단 푼다.
1번과 2번이 있고, 이 둘 중 컵라면 수는 2번 문제가 더 많이 준다.
그래서 2번을 푼다.
다음 2시간이 지났다고 생각해 보자
풀 수 있는 문제는 총 2문제이다.
데드라인이 2인 문제는 5번과 6번이며 전에 풀었다고 가정한 2번 문제를 풀지 않고 5, 6번으로 완전히 대체할 수 있다. 왜냐하면 현재 풀 수 있는 총 문제는 2문제이고, 문제 수가 2개이기 때문이다.
그래서
이 문제들과 전에 풀었던 2번 문제와 비교해서 결정한다.
결과적으로 6번을 풀어야 하며, 여기까지 2번과 6번을 풀었다고 가정한다.
이를 계속 반복하게 되면 2 6 3 7 순서로 풀었을 때 컵라면 수를 최대로 할 수 있다.
그러면 앞에서 풀었다고 가정한 모든 문제를 비교해 가며 대체를 해야할까? 아니다. 컵라면 수가 작은 순으로 정렬되어 있는 우선순위 큐를 사용해서 peek()로 비교하면 된다.
그래서 내가 푼 구체적인 방식은 list에 모든 문제를 넣고, deadline 순으로 정렬한다.
그리고 cup순으로 정렬되는 우선순위 큐를 만들고,
list를 돌면서, 현재 풀 수 있는 총 문제보다 우선순위 큐의 사이즈가 작다면 넣어주고, 같다면
peek()로 비교해서 대체할지 말지를 결정한다.
모든 list를 돌았다면, pQue에 남아있는 문제의 컵라면 수를 다 더하면 된다.
시간 복잡도는 O(N*logN)이다.
소스 코드
import java.io.*;
import java.util.*;
class HomeWork implements Comparable<HomeWork> {
int deadline, cup;
HomeWork(int deadline, int cup) {
this.deadline = deadline;
this.cup = cup;
}
@Override
public int compareTo(HomeWork o) {
if(this.cup < o.cup) {
return -1;
} else if(this.cup > o.cup) {
return 1;
}
return 0;
}
}
public class Main {
static int N;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
ArrayList<HomeWork> list = new ArrayList<>();
for(int i=0; i<N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
list.add(new HomeWork(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
}
Collections.sort(list, new Comparator<HomeWork>() {
@Override
public int compare(HomeWork h1, HomeWork h2) {
if(h1.deadline < h2.deadline) {
return -1;
} else if(h1.deadline > h2.deadline) {
return 1;
}
return 0;
}
});
PriorityQueue<HomeWork> pQue = new PriorityQueue<>();
for(int i=0; i<N; i++) {
int cp = list.get(i).deadline - pQue.size(); //현재 que에 넣을 수 있는 개수
if(cp > 0) {
pQue.add(list.get(i));
} else if(cp == 0) {
if(pQue.peek().cup < list.get(i).cup) {
pQue.poll();
pQue.add(list.get(i));
}
}
}
int answer = 0;
while(!pQue.isEmpty()) {
answer += pQue.poll().cup;
}
System.out.println(answer);
}
}