[JAVA]백준 2109: 순회강연

백준 2109: 순회강연

Link: https://www.acmicpc.net/problem/2109

풀이

• 각 강연은 우선순위가 존재(더 비싼 강연을 우선적으로)
• 강의들은 기간 제한이 존재 ( d일까지 와서 강연을 해주면 p원을 준다.)
• 제한 기간 내에 할 수 있는 강의들 중 가장 비싼 강연을 골라서 해야 함!
• 우선순위 큐를 이용.
• 강연을 날짜별로 입력받고 늦은 날부터 탐색
• 해당 일에 할 수 있는 강연을 모두 pq에 넣음.(비싼 강연이 우선)
• 날짜를 줄여가며 pq에 강연이 남아있다면 sum추가

package algorithm2023.oct.day12;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class BOJ_2109_순회강연 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	static PriorityQueue<Integer> pq = new PriorityQueue<>((o1,o2)->o2-o1);
	static ArrayList<ArrayList<Integer>> lec = new ArrayList<>();
	static int n;


	public static void main(String[] args) throws Exception {
		n = Integer.parseInt(br.readLine());
		
		for(int i =0 ;i<=10000;i++) {
			lec.add(new ArrayList<>());
		}

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			int p = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());

			lec.get(d).add(p);
			
		}
		int sum = 0;
		
		for(int i= 10000;i>0;i--) {
			for(int n : lec.get(i)) {
				pq.add(n);
			}
			if(!pq.isEmpty()) {
				sum+=pq.poll();
			}
		}
		
		System.out.println(sum);

	}
}

---

Issue

• 없음.