[BOJ] 백준 2109번 순회강연 (Java)

#2109 순회강연

난이도 : 골드 3

유형 : 그리디 / 우선순위 큐 

2109번: 순회강연

▸ 문제

한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. 각 대학에서 제시하는 d와 p값은 서로 다를 수도 있다. 이 학자는 이를 바탕으로, 가장 많은 돈을 벌 수 있도록 순회강연을 하려 한다. 강연의 특성상, 이 학자는 하루에 최대 한 곳에서만 강연을 할 수 있다.

예를 들어 네 대학에서 제시한 p값이 각각 50, 10, 20, 30이고, d값이 차례로 2, 1, 2, 1 이라고 하자. 이럴 때에는 첫째 날에 4번 대학에서 강연을 하고, 둘째 날에 1번 대학에서 강연을 하면 80만큼의 돈을 벌 수 있다.

▸ 입력

첫째 줄에 정수 n이 주어진다. 다음 n개의 줄에는 각 대학에서 제시한 p값과 d값이 주어진다.

▸ 출력

첫째 줄에 최대로 벌 수 있는 돈을 출력한다.

 

문제 풀이  

최대로 벌 수 있는 경우의 수를 체크하는 것으로 그리디 알고리즘으로 풀이가 가능하다. 짧은 d일의 높은 p 강연료를 선택하면 뒤에 있는 긴 d일의 높은 p 강연료를 하지 못할 수도 있다. 예로, (pay,day) => (10,2), (20,3), (20,3) (20,3) 가 있을 경우, 위의 그리디 탐색방식으로 하게 되면 10,20,20의 페이를 받는다.

 

그래서 이러한 케이스까지 신경을 써주려면 '높은 p 강연료를 먼저 선택하고 강연료가 같을 경우 짧은 d일을 선택한다'의 그리디 탐색을 해줘야 한다. 그러면 위의 예시를 20,20,20으로 최대로 돈을 벌 수 있게 된다. 내림차순으로 가장 높은 p강연료를 선택하고 강의 날짜는 해당 d일에 근접하게 배치해야 한다. 그래야 이후 그리디 탐색이 가능하다. 만약 가장 빠른 1일부터 채우게 된다면 뒤에 현재 강연료 p보다 같거나 높은 p2에 1일에 하는 스케줄이 있다면 해당 스케줄은 할 수 없게 된다.

 

설계

1. (day,pay)를 우선순위 큐에 저장한다. q.add(s);
   1. pay를 기준으로 내림차순 정렬한다.
   2. pay가 같을 경우, day를 오름차순 정렬한다.
2. 우선순위 큐에 저장되어 있는 모든 스케줄을 꺼내어 최대로 벌 수 있는 돈을 계산한다. q.poll();
   1. (s.day ~ 1)일 까지 해당 강의가 가능하면 값을 더해주고 해당 날짜의 스케줄을 체크한다. result += s.pay;
3. 총 계산된 result값을 출력한다.

 

풀이 코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static class Schedule implements Comparable<Schedule>{
		int day;
		int pay;
		
		public Schedule(int day, int pay){
			this.day = day;
			this.pay = pay;
		}

		@Override
		public int compareTo(Schedule o) {
			if(o.pay!= this.pay) return o.pay - this.pay;
			else return this.day-o.day;
		}
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		List<Schedule> list = new ArrayList<>();
		StringTokenizer st = null;
		int max = 0;
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			int pay = Integer.parseInt(st.nextToken());
			int day = Integer.parseInt(st.nextToken());
			max = Math.max(max, day);
			list.add(new Schedule(day, pay));
		}
		
		Queue<Schedule> q = new PriorityQueue<>();
		for(Schedule s : list) {
			q.add(s);	
		}
		
		boolean[] checked = new boolean[max+1];
		int result = 0;
		while(!q.isEmpty()) {
			Schedule s = q.poll();
			
			for(int i = s.day; i>0; i--) {
				if(!checked[i]) {
					checked[i] = true;
					result += s.pay;
					break;
				}
			}
		}
		System.out.println(result);
		
	}
}