문제는 다음과 같다.
처음 보고 배낭문제 비슷하게 풀면 되는줄 알았으나..
자세히 보니 다르다! 무조건 가방보다 작거나 같은 무게 중 비싼 애들만 담으면 되는 비교적 간단한(이게 왜 골드2..?) 문제!
package baekjoon;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class 보석도둑_1202 {
static class Jewel {
int M, V;
Jewel(int M, int V) {
this.M = M;
this.V = V;
}
}
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
PriorityQueue<Jewel> jewels = new PriorityQueue<>(new Comparator<Jewel>() {
@Override
public int compare(Jewel o1, Jewel o2) {
return Integer.compare(o1.M, o2.M);
}
});
int N = Integer.parseInt(st.nextToken()), K = Integer.parseInt(st.nextToken());
for(int i=0;i<N;i++) {
st = new StringTokenizer(bf.readLine());
jewels.offer(new Jewel(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
}
PriorityQueue<Integer> bags = new PriorityQueue<>();
for(int i=0;i<K;i++) {
bags.offer(Integer.parseInt(bf.readLine()));
}
long ans = 0;
PriorityQueue<Jewel> tempJewels = new PriorityQueue<>(new Comparator<Jewel>() {
@Override
public int compare(Jewel o1, Jewel o2) {
if(o1.V == o2.V) {
return o1.M - o2.M;
}
return o2.V - o1.V;
}
});
while(!bags.isEmpty()) {
int bag = bags.poll();
while(!jewels.isEmpty() && jewels.peek().M <= bag) {
tempJewels.offer(jewels.poll());
}
if(tempJewels.isEmpty()) {
continue;
}
ans += tempJewels.poll().V;
System.out.println(ans);
}
System.out.println(ans);
}
}
저음 보석을 받을 때 Jewel class를 만들어 pq안에 담아준다.
이때의 pq는 무게 M이 낮은 순으로 정렬되게!! (나는 값어치까지 비교하여 넣어주긴 했는데 이건 없어도 된다.)
이후 가방을 받고, 가방은 무게만 필요하니 class없이 Integer 값으로!
얘도 다른 pq에 넣어주는데, 무게가 낮은 애부터 정렬되게!! -> 정렬 조건 설정해줄 필요가 없다.
이후의 풀이를 단계별로 설명하자면,
1. bags에서 bag 한 개 poll 해온다.
2. bag 보다 작거나 같은 무게를 가진 jewel를 jewels에서 poll 한다.
3. poll한 jewel들을 tempJewels의 priority queue에 넣어준다.
* tempJewels는 값 V가 높은 순으로 정렬되게 Comparator로 정의해준다.(나는 무게까지 비교했는데 이거도 없어도 된다.)
4. tempJewels에서 poll 한 값을 정답으로 return할 값에 더해준다.
이 4가지의 단계를 bags에 남은 Integer가 없을 때까지 반복하면 된다!
그럼 정답이 뾰로롱~
곧있으면 플레 간다 야호!!
'Algorithm' 카테고리의 다른 글
| [boj] 최소 편집_15483JAVA (0) | 2024.09.16 |
|---|---|
| [boj] 수업시간에 교수님 몰래 교실을 나간 상근이_2825 JAVA (4) | 2024.09.08 |
| [boj] RGB거리 2_17404 JAVA (0) | 2024.09.01 |
| [boj] 비슷한 단어_2179 JAVA (0) | 2024.08.18 |
| [boj] 민식어_1599 java (0) | 2024.08.04 |
