https://www.acmicpc.net/problem/1202
1202번: 보석 도둑
첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci
www.acmicpc.net
문제설명
보석이 총 N개가 주어집니다. 순서대로 보석의 무게와 보석의 가격입니다. N개가 주어진 후 가방이 K개 주어집니다.
위 예제에서는 11의 가방에는 100이 못들어가므로 5를 집어넣고 가격의 최댓값은 10입니다.
문제에 대한 아이디어
간단하게 생각해서 보석을 가격을 기준으로 내림차순으로 새팅 한 뒤, 가방과 무게와 보석 무게가 차이가 제일 적게 나는 가방을 찾아 선택해 주면 될 것 같습니다. 하지만 이렇게 할 경우 당연히 시간초과가 날 것입니다.
중요한 점은 보석 검사를 중복해서 안하게 하는 게 키포인트라고 생각합니다.
- 이미 선택한 것은 검사를 안하게 한다.
- 선택을 안했더라도 for문에서 지나온 것은 다시 검사를 하면 안 된다.
즉, 가방의 개수만큼 for문을 돌면서 알맞은 보석을 중복 검사 없이 선택해 주면 됩니다.
- 보석을 무게를 오름차순으로 무게가 동일할 시 가격을 내림차순으로 정렬합니다.
- 가방을 오름차순으로 정렬합니다.
이렇게 하면 첫 번째 가방에 들어갈 보석을 선택한다고 가정하면 보석 Array를 돌면서 가방보다 작은 무게의 보석을 모두 우선순위 큐에 집어 넣습니다. 이때, 우선순위 큐는 가격을 기준으로 내림차순입니다. 이렇게 하면 2번째 가방을 검사할 때는 무조건 첫번째 가방보다 가방에 들어갈 보석 무게가 더 클 것이고 우선순위큐에는 첫번째 가방보다 무게가 작은 보석들이 들어가 있습니다. 그러므로 보석들을 처음부터 중복검사를 안 해도 됩니다!!
이런 문제를 풀면서 느낀 점은 우선순위큐와 그리디는 밀접한 관련이 있다는 것입니다. 그리고 보통 이렇게 그리디로 문제를 풀 때는 정렬의 기준이 중요합니다. 어떤 것을 정렬할지만 잘 생각하면 좀 더 쉽게 문제를 풀어나갈 수 있을 것 같습니다.
그리디 VS DP
알고리즘 문제를 많이 풀면 느끼는 고민 이 문제는 그리디로 풀까 DP로 풀까???
GPT가 말해주는 해결책입니다. 하지만 너무 추상적입니다. 제가 생각하는 결정법은 예시를 해보다가 너무 경우의 수와 고려해 줄게 많다. 그러면 백트래킹을 사용한 브루트포스 고려 근데 input 값이 너무 많다 그러면 바로 DP 생각.
경우의 수가 별로 없고 바로바로 최적을 선택할 방법이 하나다. 그러면 그리디를 선택하면 될 것 같습니다. 위 문제처럼 바로바로 최고 가격을 선택하면 되는 문제는 의심의 여지없이 그리디를 선택하면 됩니다,
전체 코드
import java.util.*;
import java.io.*;
public class 백준_1202_보석_도둑 {
public static class Pair implements Comparable<Pair>{
int m,v;
public Pair(int m, int v){
this.m = m;
this.v = v;
}
public int compareTo(Pair p){
if(this.m == p.m) return p.v - this.v;;
return this.m - p.m;
}
}
public static void main(String[] args) throws IOException {
BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(buf.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
ArrayList<Pair> jew = new ArrayList<>(); // 보석
ArrayList<Integer> bag = new ArrayList<>(); // 가방
for(int i = 0; i < n; ++i){
st = new StringTokenizer(buf.readLine());
int m = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
jew.add(new Pair(m,v));
}
for(int i = 0; i < k; ++i){
st = new StringTokenizer(buf.readLine());
bag.add(Integer.parseInt(st.nextToken()));
}
Collections.sort(jew);
Collections.sort(bag);
long answer = 0;
// 검사한 보석을 넣을 우선순위큐
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
for(int i = 0, j = 0; i < k; ++i){
while(j < n && jew.get(j).m <= bag.get(i)){
pq.add(jew.get(j++).v);
}
if(!pq.isEmpty()){
answer += pq.poll();
}
}
System.out.println(answer);
}
}
