[백준] 2109 - 순회강연

[문제링크]

2109번: 순회강연

 

0. 과제 문제와 거의 동일한 문제 (링크)

 

1. N일까지인 강연을 N-1일에는 갈 수 있지만, N+1일에 가는것은 불가능하다

 

2. 가능한 마지막날부터 시작해 탐색하며, 그날그날 최고 보수의 강의를 선택한다

 

3. 과제 문제와 달리 강의 의뢰가 아예 들어오지 않을 수 있으므로, (0, 0)인 가상의 과제를 만들어 제공한다

 

import java.io.BufferedReader;
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{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = pint(br.readLine());
		
		int[][] recture = new int[N+1][2];
		
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			recture[i][0]=pint(st.nextToken());
			recture[i][1]=pint(st.nextToken());
		}
		
		Arrays.sort(recture, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				// TODO Auto-generated method stub
				return o2[1]-o1[1];
			}
		});
		
		int day = recture[0][1];
		int i=0;
		int money=0;
		PriorityQueue<Integer>pq = new PriorityQueue<>(Collections.reverseOrder());
		
		while(day!=0) {
			while(i<recture.length && recture[i][1]==day) {
				pq.add(recture[i][0]);
				i++;
			}
			day--;
			if(!pq.isEmpty())money+=pq.poll();
		}
		System.out.println(money);
		
		
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
	
}

결과 화면