[BOJ 1202] 보석 도둑

문제

보석 도둑

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

 

 

풀이

설명

훔칠 수 있는 보석 가격의 합의 최댓값을 구하는 문제입니다.

 

그리디 알고리즘과 우선순위 큐를 사용해 해결할 수 있습니다.

 

보석은 무게를 기준으로 오름차순, 가방은 오름차순으로 정렬합니다.

 

가방을 순회하면서 현재 가방에 담을 수 있는 모든 보석을 큐에 추가합니다.

큐에는 가방에 담을 수 있는 보석들이 가격이 비싼 순으로 들어 있습니다.

큐 추가 작업이 끝나면 가장 비싼 보석을 꺼내 결과에 더해줍니다.

 

예시 코드

function solution() {
  const [n, k] = input().split(" ").map(Number);
  const gems = Array.from({ length: n }, () => input().split(" ").map(Number));
  const bags = Array.from({ length: k }, () => Number(input()));
  let gemIdx = 0;
  let answer = 0;

  gems.sort((a, b) => a[0] - b[0]);
  bags.sort((a, b) => a - b);

  const pq = new PriorityQueue();

  for (const bag of bags) {
    while (gemIdx < n && gems[gemIdx][0] <= bag) {
      pq.enqueue(gems[gemIdx][1]);
      gemIdx++;
    }

    if (!pq.isEmpty()) {
      answer += pq.dequeue();
    }
  }

  return answer;
}