백준 1202 : 보석 도둑

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

1202번: 보석 도둑

 

접근 방법

---

해당 문제는 그리디 알고리즘을 이용해 풀 수 있습니다.

보석의 최대 가격을 구하기 위해서는 각각의 가방에 넣을 수 있는 보석 중 최대 가격을 가진 보석을 넣어야 합니다.

결국, 각 가방에 담을 수 있는 최대 무게보다 작은 보석 중에서 제일 큰 가격을 가지고 있는 보석을 선택하면 됩니다.

 

하지만 보석을 넣을 때는 최대 무게가 작은 가방부터 넣어야 합니다.

예를 들어 (무게 : 10, 가격 : 10), (무게 : 5, 가격 : 20)인 보석이 있고 (최대 무게 : 10), (최대 무게 : 5)인 가방이 있다고 가정해 보겠습니다.

(최대 무게 : 10)인 가방부터 생각한다면 해당 가방에 넣을 수 있는 보석 중 가장 가격이 높은 보석은 (무게 : 5, 가격 : 20)인 보석입니다. 해당 보석을 가방에 넣게 되면 다른 가방에는 아무것도 넣을 수 없습니다.

이 결과는 보석의 최대 가격이라 할 수 없습니다.

 

이를 가방의 최대 무게가 작은 것부터 계산한다면 최대 가격을 구할 수 있습니다.

 

 

순서

---

1.  보석과 가방을 무게 순으로 오름차순 정렬
2.  각 가방에 넣을 보석 찾기
   1.  해당 가방의 최대 무게보다 작거나 같으면서 그 전 가방의 최대 무게보다 무게가 큰 모든 보석 priority queue에 넣기
   2.  queue에서 pop을 통해 queue에서 가장 가격의 높은 보석 찾기
3. 각 가방의 보석의 가격 합 구하기

2.1 과정을 사용하면 모든 보석을 한번 씩만 탐색하고도 정답을 구할 수 있습니다.

 

 

코드

---

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

public class Main {
	static int N, K;
	static long ans = 0;
	static int[] backpackList;
	static jewelry[] jewelryList;
	static PriorityQueue<Integer> pq;
	
	static class jewelry implements Comparable<jewelry>{
		int M, V;

		public jewelry(int m, int v) {
			super();
			M = m;
			V = v;
		}

		@Override
		public int compareTo(jewelry o) {
			return this.M - o.M;
		}
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		jewelryList = new jewelry[N];
		backpackList = new int[K];
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			jewelryList[i] = new jewelry(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
		}
		
		for (int i = 0; i < K; i++) {
			backpackList[i] = Integer.parseInt(br.readLine());
		}
		
		Arrays.sort(jewelryList);
		Arrays.sort(backpackList);
		
		int idx = 0;
		pq = new PriorityQueue<>(Collections.reverseOrder());
		for (int i = 0; i < K; i++) {
			int c = backpackList[i];
			
			while(idx < N && jewelryList[idx].M <= c)
				pq.offer(jewelryList[idx++].V);
			
			if(!pq.isEmpty())
				ans += pq.poll();
		}
		
		System.out.print(ans);
	}
}

 

Reference

---

https://jaimemin.tistory.com/760