[백준] 1202번 : 보석 도둑

문제

1202번: 보석 도둑

 

 

접근 방식

m	v
1	65
2	98
2	95
5	99
5	96
5	90

 

보석의 무게와 가치를 위와 같이 무게가 가벼운 순으로, 같다면 가치가 높은 순으로 정렬한 후에

오름차순으로 정렬된 가방을 하나씩 보면서 현재 가방의 무게 이하인 보석을 모두 우선순위 큐에 넣고

가장 큰 값을 하나만 꺼내서 누적합에 더해주면 된다.

2
2
10
10

 

가방의 무게가 다음과 같을 때

[2]	98 95 65
[2]	95 65
[10]	99 96 90 65
[10]	96 90 65

 

처음 가방 무게가 2일 때는 98, 95, 65를 추가하고 그중에서 가장 큰 98을 큐에서 꺼내고

다음 가방 무게가 2일 때도 남은 95, 65 중에서 95를 꺼낸 후에

가방 무게가 10일 때 99와 90을 추가한 후에 가장 큰 99를 꺼내고

마지막 가방 무게가 10일 때 남은 96, 90, 65 중에서 가장 큰 96을 꺼낸다.

 

 

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		long max = 0;

		PriorityQueue<Gem> gems = new PriorityQueue<>();
		PriorityQueue<Integer> bags = new PriorityQueue<>();
		PriorityQueue<Integer> values = new PriorityQueue<>(Comparator.reverseOrder());

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());

			int m = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());

			gems.offer(new Gem(m, v));
		}

		for (int i = 0; i < k; i++) {
			int c = Integer.parseInt(br.readLine());
			bags.offer(c);
		}

		while (!bags.isEmpty()) {
			int bag = bags.poll();

			while (!gems.isEmpty()) {
				Gem gem = gems.peek();

				if (gem.m > bag) break;

				gems.poll();
				values.offer(gem.v);
			}

			if (!values.isEmpty()) max += values.poll();
		}

		System.out.println(max);
	}

	static class Gem implements Comparable<Gem> {
		int m, v;

		Gem(int m, int v) {
			this.m = m;
			this.v = v;
		}

		@Override
		public int compareTo(Gem o) {
			return this.m != o.m ? this.m - o.m : o.v - this.v;
		}
	}
}