[Java] BOJ 1202 - 보석 도둑

 

 

BOJ 1202 - 보석 도둑 (https://www.acmicpc.net/problem/1202)

 

01. 🔎 문제 탐색

N: 보석의 개수, K: 가방의 개수
$M_i, V_i$: 보석의 무게와 가치
$C_i$: 가방에 담을 수 있는 보석의 최대 무게

• 하나의 가방에는 하나의 보석만 담을 수 있음
• 각 가방에 보석을 담았을 때, 가져갈 수 있는 최대 가치를 출력

01-1. 알고리즘 선택 & 시간 복잡도

• 각 가방에 주어진 무게에 대해, 넣을 수 있는 최대 가치의 보석을 넣으면 되는 그리디 문제
• 정렬을 통해 보석과 가방을 오름차순으로 정렬 후, 탐색하여 담을 수 있는 보석을 알 수 있음
• 담을 수 있는 보석을 판단 후, 우선순위큐를 이용하여 그 중 최대 가치를 골라낼 수 있음

02. 📝 코드 설계하기

1. 보석과 가방의 정보를 입력
2. 보석과 가방을 오름차순으로 정렬
3. 가방을 순차적으로 탐색
   1. 현재 선택된 가방에 들어갈 수 있는 보석을 탐색하여 우선순위큐에 넣음
4. 우선순위큐에 요소가 있다면 최대 값을 꺼내어 가방에 넣고(합계 누적), 없다면 아무것도 넣지 않음
5. 가방 안에 들어간 보석의 가치(총합)를 출력

03. 🛠️ 시도별 수정

---

04. 🗝️ 정답 코드

import java.io.*;
import java.util.*;

public class Main {
  static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
  static StringTokenizer st;

  public static class Pair implements Comparable<Pair>{
    int M, V;
    Pair(int m, int v){
      this.M = m;
      this.V = v;
    }

    @Override
    public int compareTo(Pair o){
      return this.M - o.M;
    }
  }

  static int N, K;
  static Pair[] jewel;
  static int[] bag;

  public static void main(String[] args) throws IOException {
    st = new StringTokenizer(br.readLine());
    N = Integer.valueOf(st.nextToken());
    K = Integer.valueOf(st.nextToken());

    jewel = new Pair[N];
    for(int i = 0; i < N; i++){
      st = new StringTokenizer(br.readLine());
      int m = Integer.valueOf(st.nextToken());
      int v = Integer.valueOf(st.nextToken());

      jewel[i] = new Pair(m, v);
    }
    Arrays.sort(jewel);

    bag = new int[K];
    for(int i = 0; i < K; i++){
      int c = Integer.valueOf(br.readLine());
      bag[i] = c;
    }
    Arrays.sort(bag);

    PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());

    long sum = 0;
    int idx = 0;
    for(int i = 0; i < K; i++){
      int bagSize = bag[i];

      while(idx < N && jewel[idx].M <= bagSize){
        pq.offer(jewel[idx].V);
        idx++;
      }

      if(!pq.isEmpty()) sum += (1L*pq.poll());
    }
    
    bw.write(sum + "\n");

    bw.flush();
    bw.close();
    br.close();
  }
}