BOJ 1202 - 보석 도둑

보자마자 떠오르는 건 그리디와 정렬이었다. 약간의 시행 착오를 거친 뒤에, 수용량이 작은 가방부터 담을 수 있는 최대 가치의 보석을 담는다면 답을 얻을 수 있다는 결론을 내리고 코드를 쳤다.

1. 수용량이 작은 가방부터 차례로 꺼낸다.
2. 입력받은 보석을 무게를 기준으로 오름차순 정렬한다.
3. 보석의 가치 순으로 내림차순 정렬하는 우선순위 큐에 가방이 수용 가능한 무게의 보석들을 옮긴다.
4. 우선순위 큐의 첫번째 보석을 꺼내 값에 더해준다.

삭제과정 없이 간단하게 poll해서 사용하기 위해 모든 정렬을 우선순위 큐를 통해서 했다.

class Jewel{
    int weight;
    int value;
    Jewel(int weight, int value){
        this.weight = weight;
        this.value = value;
    }
}

public class Main {

    static int N;
    static int K;
    
    // 수용량이 작은 가방부터 꺼낼 수 있는 pq
    static PriorityQueue<Integer> bags = new PriorityQueue<>();
    
    // 가치가 높은 보석부터 꺼낼 수 있는 pq
    static PriorityQueue<Jewel> pq = new PriorityQueue<>( (e1,e2)->{
        return e2.value - e1.value;
    });
    
    // 낮은 무게 순으로 꺼낼 수 있는 pq
    static PriorityQueue<Jewel> jewels = new PriorityQueue<>( (e1,e2)->{
        return e1.weight - e2.weight;
    });

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        long answer = 0;

        for(int i = 0 ; i<N; i++){
            st = new StringTokenizer(br.readLine());
            int weight = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());

            jewels.add(new Jewel(weight, value));
        }

        for(int i = 0; i<K; i++){
            int weight = Integer.parseInt(br.readLine());
            bags.add(weight);
        }

		// 가방이 없을 때 까지
        while(!bags.isEmpty()){
            int weight = bags.poll();

			// 남은 보석이 있고, 보석의 무게가 가방의 수용량 이하라면 pq로 옮겨준다
            while(!jewels.isEmpty() && jewels.peek().weight <= weight){
                pq.add(jewels.poll());
            }
            // 가방에 담을 수 있는 보석이 없다면 continue
            if(pq.isEmpty()) continue;
            answer += pq.poll().value;
        }

        System.out.println(answer);
    }
}