이번에 풀어본 문제는
백준 1202번 보석 도둑 입니다.

📕 문제 링크

❗️코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Gem
{
    int m,v;

    public Gem(int m, int v) {
        this.m = m;
        this.v = v;
    }
}
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());

        List<Gem> gems = new ArrayList<>();
        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.add(new Gem(m,v));
        }

        gems.sort((o1, o2) -> {
            if (o1.m == o2.m) return o2.v - o1.v;
            return o1.m - o2.m;
        });

        List<Integer> bags = new ArrayList<>();
        for(int i = 0; i < K; ++i)
        {
            bags.add(Integer.parseInt(br.readLine()));
        }
        Collections.sort(bags);

        int gem_idx = 0;
        int gem_size = gems.size();
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        long answer = 0;
        for(int bag : bags)
        {
            while(gem_idx < gem_size && bag >= gems.get(gem_idx).m) pq.add(gems.get(gem_idx++).v);

            if(!pq.isEmpty()) answer += pq.poll();
        }
        System.out.println(answer);
    }
}

📝 풀이

무게와 비용을 지닌 N개의 보석들을 K개의 가방에 담을 때, 최대의 비용을 발생시킬 수 있는 경우를 구하는 문제입니다. K개의 가방은 각각 C만큼의 무게를 견딜 수 있습니다.
먼저 보석들의 무게와 비용이 다르므로 가장 효율적인 선택을 위해 정렬이 필요합니다. 저는 가방의 무게를 기준으로 가장 적은 무게를 버틸 수 있는 가방부터 순차적으로 채워야 한다고 생각하고 정렬을 진행했습니다.
위의 조건에 맞추기 위해, 가방은 버틸 수 있는 무게를 기준으로 오름차순 정렬했고, 그에 따라 보석도 무게를 기준으로 오름차순이 됩니다. 무게가 같을경우, 비용은 비싸야 하므로 비용 기준 내림차순 정렬해줍니다.
정렬을 마치면, 가방을 탐색하며 무게가 가벼운 가방부터 보석을 선택합니다. 현재 가방의 무게로 담을 수 있는 보석이라면, 우선순위 큐에 담아줍니다. 현재 가방의 무게로 수용 가능한 보석을 모두 담았다면, 큐의 최상단 값을 꺼내줍니다. 그러면 현재 가방으로 담을 수 있는 최대 비용의 보석을 얻을 수 있습니다. 해당 과정을 끝까지 반복해주면 해결됩니다.

📜 후기

처음엔 큐를 두개 사용해볼까 했지만, 입력 범위가 너무 커서 조금 다른 방법으로 접근해 보았습니다. 두개를 사용했을 때 시간초과가 나올지 조금 궁금하긴 합니다 ㅋㅋ