728x90
문제
접근 방식
m v
1 65
2 98
2 95
5 99
5 96
5 90
보석의 무게와 가치를 위와 같이 무게가 가벼운 순으로, 같다면 가치가 높은 순으로 정렬한 후에
오름차순으로 정렬된 가방을 하나씩 보면서 현재 가방의 무게 이하인 보석을 모두 우선순위 큐에 넣고
가장 큰 값을 하나만 꺼내서 누적합에 더해주면 된다.
2
2
10
10
가방의 무게가 다음과 같을 때
[2] 98 95 65
[2] 95 65
[10] 99 96 90 65
[10] 96 90 65
처음 가방 무게가 2일 때는 98, 95, 65를 추가하고 그중에서 가장 큰 98을 큐에서 꺼내고
다음 가방 무게가 2일 때도 남은 95, 65 중에서 95를 꺼낸 후에
가방 무게가 10일 때 99와 90을 추가한 후에 가장 큰 99를 꺼내고
마지막 가방 무게가 10일 때 남은 96, 90, 65 중에서 가장 큰 96을 꺼낸다.
풀이
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
long max = 0;
PriorityQueue<Gem> gems = new PriorityQueue<>();
PriorityQueue<Integer> bags = new PriorityQueue<>();
PriorityQueue<Integer> values = new PriorityQueue<>(Comparator.reverseOrder());
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
int m = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
gems.offer(new Gem(m, v));
}
for (int i = 0; i < k; i++) {
int c = Integer.parseInt(br.readLine());
bags.offer(c);
}
while (!bags.isEmpty()) {
int bag = bags.poll();
while (!gems.isEmpty()) {
Gem gem = gems.peek();
if (gem.m > bag) break;
gems.poll();
values.offer(gem.v);
}
if (!values.isEmpty()) max += values.poll();
}
System.out.println(max);
}
static class Gem implements Comparable<Gem> {
int m, v;
Gem(int m, int v) {
this.m = m;
this.v = v;
}
@Override
public int compareTo(Gem o) {
return this.m != o.m ? this.m - o.m : o.v - this.v;
}
}
}
'Java > Algorithms' 카테고리의 다른 글
[백준] 11054번 : 가장 긴 바이토닉 부분 수열 (1) | 2024.04.20 |
---|---|
[백준] 18352번 : 특정 거리의 도시 찾기 (0) | 2024.04.18 |
[백준] 16946번 : 벽 부수고 이동하기 4 (0) | 2024.04.15 |
[백준] 2239번 : 스도쿠 (0) | 2024.04.13 |
[백준] 15659번 : 연산자 끼워넣기 (3) (0) | 2024.04.12 |