[BOJ] 백준 1202. 보석도둑

문제

https://www.acmicpc.net/problem/1202

1202번: 보석 도둑

---

풀이

 우선 순위 큐를 이용해 문제를 해결했습니다. 단순히 반복문 두 개로도 해결할 수는 있지만, 시간 복잡도가 300,000*300,000으로 제한 범위를 훨씬 넘어가게 됩니다.

 

 

 풀이 방법은 다음과 같습니다.

 

 1. 우선 보석을 무게에 대해 오름차순으로 정렬합니다. 그리고 무게가 같다면 가격에 대해 내림차순 정렬합니다.

 2. 가방은 배열에 담아 오름차순으로 정렬합니다.

 3. 가방에 대한 반복문을 돌립니다.

  3-1. 가방을 돌면서 가방보다 무게가 작은 보석을 우선순위 큐에 집어 넣습니다. 이때 우선 순위 큐는 가격에 대한 내림차순 정렬입니다.

  3-2. 큐가 비어있지 않다면, 가방에 넣을 수 있는 보석이 있다는 것이고 queue.poll을 통해 맨 앞 요소를 정답에 더해줍니다. 만약 큐가 비어있다면 가방에 넣을 수 있는 보석이 없다는 것입니다.

---

소스코드

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

public class B1202_보석도둑 {
    static Scanner sc = new Scanner(System.in);
    static int N,K;
    static int[] bags;
    static long ans;
    static class Gemstone implements Comparable<Gemstone>{
        int weight;
        int cost;
        Gemstone(int weight, int cost){
            this.weight = weight;
            this.cost = cost;
        }
        @Override
        public int compareTo(Gemstone g){
            if(weight==g.weight) return g.cost-cost;
            return weight-g.weight;
        }
    }
    static PriorityQueue<Gemstone> gemstones = new PriorityQueue<>();

    public static void main(String[] args) {
        input();
        Arrays.sort(bags);
        findMaxSum();
        System.out.println(ans);
    }

    static void input(){
        N = sc.nextInt();
        K = sc.nextInt();
        bags = new int[K];
        for(int i = 0;i<N;i++){
            int w = sc.nextInt();
            int c = sc.nextInt();
            gemstones.add(new Gemstone(w,c));
        }
        for(int i =0;i<K;i++){
            bags[i] = sc.nextInt();
        }
    }
    static void findMaxSum(){
        PriorityQueue<Gemstone> queue = new PriorityQueue<>(new Comparator<Gemstone>() {
            @Override
            public int compare(Gemstone o1, Gemstone o2) {
                return o2.cost - o1.cost;
            }
        });

        for(int i = 0;i<K;i++){
            while(!gemstones.isEmpty()&&gemstones.peek().weight<=bags[i]) queue.add(gemstones.poll());
            if(!queue.isEmpty()) ans+= queue.poll().cost;
        }
    }
}