사용한 것
- 훔칠 수 있는 보석의 최대 가격을 구하기 위한 그리디
- 가방에 넣을 수 있는 보석 중 가장 큰 가치를 고르기 위한 우선순위 큐
풀이 방법
items
에 보석들을 무게 오름차순, 무게가 같으면 가치 내림차순으로 저장한다.
bags
에 가방의 무게 오름차순으로 저장한다.
- 훔칠 수 있는 보석들 중 가장 큰 가치의 보석을 빼내기 위한
pq
를 사용한다.
- 반복문을 돌며 현재 가방에 들어갈 수 있는 보석들을
pq
에 넣는다.
- 더 이상 가방에 들어갈 수 있는 보석들이 없다면
pq
에서 가장 큰 가치의 보석을 하나 빼내어 answer
에 더한다.
- 다음 가방의 경우 이전 가방보다 무게가 크기 때문에 이미
pq
에 저장된 보석들도 무조건 가방에 들어갈 수 있다.
코드
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] line = br.readLine().split(" ");
int n = Integer.parseInt(line[0]);
int k = Integer.parseInt(line[1]);
Item[] items = new Item[n];
for (int i = 0; i < n; i++) {
line = br.readLine().split(" ");
int m = Integer.parseInt(line[0]);
int v = Integer.parseInt(line[1]);
items[i] = new Item(m, v);
}
Bag[] bags = new Bag[k];
for (int i = 0; i < k; i++) {
int c = Integer.parseInt(br.readLine());
bags[i] = new Bag(c);
}
Arrays.sort(items);
Arrays.sort(bags);
long answer = 0;
PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
int j = 0;
for (int i = 0; i < k; i++) {
while (j < n && items[j].m <= bags[i].c) {
pq.offer(items[j++].v);
}
if (!pq.isEmpty()) {
answer += pq.poll();
}
}
System.out.println(answer);
}
}
class Item implements Comparable<Item> {
public int m;
public int v;
public Item(int m, int v) {
this.m = m;
this.v = v;
}
@Override
public int compareTo(Item o) {
if (this.m == o.m) {
return o.v - this.v;
} else {
return this.m - o.m;
}
}
}
class Bag implements Comparable<Bag> {
public int c;
public Bag(int c) {
this.c = c;
}
@Override
public int compareTo(Bag o) {
return this.c - o.c;
}
}