백준 1202 - 보석도둑

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

1202번: 보석 도둑

문제 설명

세계적인 도둑 상덕이는 보석점을 털기로 결심했다.

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)

다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)

다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)

모든 숫자는 양의 정수이다.

 

문제 풀이

일단, 입력으로 들어올 수 있는 최대 보석의 갯수가 30만개, 가방이 30만개이다. 가방에는 최대 한개의 보석만 넣을 수 있기 때문에, 완전 탐색으로 모든 보석과 모든 가방을 비교했을 경우 300,000^2 으로 900억이 나오기 때문에 시간초과가 날 것이다.

그래서 그리디적으로 생각해서 보석의 가치를 기준으로 내림차순 정렬을 해준 뒤, 해당 보석을 담을 수 있는 제일 작은 가방을 찾으려고 했다.

그러기 위해서는 가방의 크기 또한 정렬이 되어 있어야 했고, Key-Value와 같은 형식으로 기록을 할 수 있어야 했다.

위와 같은 이유로 자료구조는 TreeMap를 선택했다. 트리맵은 Key-Value와 같은 형식으로 데이터를 저장하는데, Key값을 기준으로 정렬해준다.

이와 같은 특징을 활용하여 Key에는 가방의 크기를, Value에는 1을 넣어서 가방의 사용 유무를 판단하기로 했다.

보석의 가치를 기준으로 정렬된 PriorityQueue를 활용해 값을 하나씩 뽑아 가며 가방에 담으며, 사용중인 가방은 map에서 제거하고, 해당 보석의 가치를 계속해서 더해주었다.

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.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class Main {
	public static class 보석 implements Comparable<보석>{
		int weight;
		int value;
		public 보석(int weight, int value) {
			super();
			this.weight = weight;
			this.value = value;
		}
		@Override
		public int compareTo(보석 o) {
			return this.value<o.value?1:-1;
			
		}
		@Override
		public String toString() {
			return "보석 [weight=" + weight + ", value=" + value + "]";
		}
	}
	static int N,K,count,max;
	static long sum;
	static PriorityQueue<보석> pq = new PriorityQueue<>();
	static TreeMap<Integer, Integer> 가방 = new TreeMap<>();
	static boolean[] visited;
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		visited = new boolean[K];
		max = Integer.MIN_VALUE;
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			int weight = Integer.parseInt(st.nextToken());
			int value = Integer.parseInt(st.nextToken());
			pq.add(new 보석(weight, value));
		}
		for(int i=0; i<K; i++) {
			int size = Integer.parseInt(br.readLine());
			if(가방.containsKey(size)) {
				가방.put(size, 가방.get(size)+1);
			}
			else {
				가방.put(size, 1);
			}
			max = Math.max(max, size);
		}
		
		while(!pq.isEmpty()) {
			if(count>=K) break;
			보석 temp = pq.poll();
			if(temp.weight>max) continue;
			
			Integer val = 가방.ceilingKey(temp.weight);
			if(val != null) {
				가방.put(val, 가방.get(val)-1);
				if(가방.get(val)==0) {
					가방.remove(val);
				}
				sum+=temp.value;
			}
		}
		System.out.println(sum);
	}
}