Java

[백준 1202] 보석도둑 (JAVA)

iheeeee6-6 2023. 2. 3. 16:21
728x90

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

1202번: 보석 도둑

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci

www.acmicpc.net


우선순위 큐를 사용하여 이 문제를 해결할 수 있었다!

1. 무게와 가격을 가진 보석 객체를 생성하여 무게 오름차순 정렬한다.
2. 가방 무게 오름차순 정렬한다.
3. 가방 전체를 돌면서 해당하는 무게에 들어 갈 수 있는 보석의 가격을 우선순위 큐에 넣는다. ( 우선순위 큐는 내림차순정렬)

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

public class Main {
	static int n, k;
	static int[] karr;

	static class Jewel {
		int g;
		int price;

		Jewel(int g, int price) {
			this.g = g;
			this.price = price;
		}

		int getG() {
			return g;
		}

		int getPrice() {
			return price;
		}
	}

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

		Jewel[] jewel = new Jewel[n];
		karr = new int[k];
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			int g = Integer.parseInt(st.nextToken());
			int price = Integer.parseInt(st.nextToken());
			jewel[i] = new Jewel(g, price);
		}
		for (int i = 0; i < k; i++) {
			karr[i] = Integer.parseInt(br.readLine());
		}

		Arrays.sort(jewel, new Comparator<Jewel>() {
			public int compare(Jewel j1, Jewel j2) {
				return j1.getG() - j2.getG();
			}
		});

		Arrays.sort(karr);

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

		long result = 0;
		int idx = 0;
		for (int i = 0; i < k; i++) {
			while (idx < n && jewel[idx].g <= karr[i]) { //가방은 무게 오름차순으로 되어 있기에 i=0번째에 들어가는 거는 i=1에도 가능..
				pq.add(jewel[idx++].price);
			}

			if (!pq.isEmpty())
				result += pq.poll();
		}

		System.out.println(result);
	}

}

'Java' 카테고리의 다른 글

[백준 2133] 타일 채우기 (JAVA)  (0) 2023.02.05
[백준 1439] 뒤집기 (JAVA)  (0) 2023.02.04
[백준 7576] 토마토 풀이 (JAVA)  (0) 2023.02.03
[백준 14888] 연산자 끼워넣기 (JAVA)  (0) 2023.02.02
[백준 9663] N-Queen 풀이 (JAVA)  (0) 2023.02.02