[백준BOJ] 1202번 보석 도둑.java

 

백준 저지에서 보석 도둑을 자바를 통해 풀어 보았다. 

 

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

1202번: 보석 도둑

1202번 보석 도둑.java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

1202번 보석 도둑 

문제

세계적인 도둑 상덕이는 보석점을 털기로 결심했다.
상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.
상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

설명

우선순위 큐를 활용해서 문제를 풀 수 있다.

 

가방에는 가방에 들어갈 수 있으면서 가치가 가장 큰 보석을 넣어야 한다. 가져갈 수 있는 보석의 개수는 가방의 개수와 같다. 

 

두 가방 A,B가 있다고 가정하자. A가 B보다 크다면 B에 넣을 수 있는 모든 보석은 A에도 넣을 수 있다. 이 사실과 우선순위 큐를 활용해야 한다. 

 

가방은 크기 순, 보석은 무게 순으로 정렬한다. 이중 포문을 통해 각 가방에 대하여 넣을 수 있는 모든 보석을 확인한다. 가방에 넣을 수 있다면 해당 보석은 더 이상 확인하지 않는다. 가방을 크기 순으로 정렬했기때문에 다음 가방에도 무조건 들어갈 수 있기 때문이다. 가방에 넣을 수 있는 보석은 우선순위 큐에 삽입한다. 우선순위 큐에 들어갔다는 것은 현재 가방에 넣을 수 있는 보석이란 뜻이다.

 

바깥 반복문마다 우선순위 큐에서 하나의 보석을 빼서 가방에 넣는다. 즉 우선순위 큐는 최대 힙이다. 현재 가방에 들어갈 수 있는 보석 중 가장 가치가 큰 보석을 선택한 것이다. 

 

아래 코드는 정답 코드의 이중 포문만 가져온 것이다.

int d = 0;
for(int i=0;i<K;i++) {
  for(int j=d;j<N;j++) {
    if(bags[i] >= diaes[j].M) {
      pq.add(-1*diaes[j].V);
      d++;
    }
    else break;
  }
  if(!pq.isEmpty()) {
    answer+=-1*pq.poll();
  }
}

바깥 for문은 현재 가방이다. 가방은 크기 순으로 정렬되어 있다. 

안 for문은 현재 보석이다. 가방에 들어갈 수 있는지 확인한다. 만약 현재 가방에 들어갈 수 있는 보석이라면 이후 가방에서도 들어갈 수 있는 보석이다. 따라서 다음 가방에서는 굳이 비교할 필요가 없다. 비교를 피하기 위해 안 for문의 시작 index인 d를 1 증가시킨다. 

 

바깥 for문의 한 반복마다 가방에 어떤 보석을 넣을지 정해야한다. 가방에 들어갈 수 있는 모든 보석 중 가장 가치가 큰 보석을 선택해야한다. 이를 위해 보석을 우선순위 큐에 넣는 것이다. 우선순위 큐에는 현재 가방에 들어갈 수 있는 보석들이 삽입되어 있다. 그 중 가치가 가장 큰 보석을 가방에 넣는다. 

 

코드

//1202번 보석 도둑.java
package boj20211214;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class 보석_도둑_1202 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    
    static class dia implements Comparable<dia>{
    	int M;
    	int V;
    	dia(int M, int V){
    		this.M = M;
    		this.V = V;
    	}
		@Override
		public int compareTo(dia o) {
			return Integer.compare(this.M, o.M);
		}
    }
    static class bag implements Comparable<bag>{
    	int C;
    	bag(int C){
    		this.C = C;
    	}
		@Override
		public int compareTo(bag o) {
			return Integer.compare(this.C, o.C);
		}
    }
    
    public static void main(String[] args) throws IOException {
    	long answer = 0;
    	
		st = new StringTokenizer(br.readLine()," ");
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		dia[] diaes = new dia[N];
		int[] bags = new int[K];
		
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine()," ");
			int M = Integer.parseInt(st.nextToken());
			int V = Integer.parseInt(st.nextToken());
			diaes[i] = new dia(M, V);
		}
		for(int i=0;i<K;i++) {
			bags[i] = Integer.parseInt(br.readLine());
		}
		
		Arrays.sort(diaes);
		Arrays.sort(bags);
		
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		
		int d = 0;
		for(int i=0;i<K;i++) {
			for(int j=d;j<N;j++) {
				if(bags[i] >= diaes[j].M) {
					pq.add(-1*diaes[j].V);
					d++;
				}
				else break;
			}
			if(!pq.isEmpty()) {
				answer+=-1*pq.poll();
			}
		}
		
		System.out.println(answer);
	}
}