[알고리즘] 백준 2109 : 순회강연 - JAVA

문제

---

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값이 주어진다.

 

출력

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

 

풀이

---

문제를 풀며 주의해야 할 점은 두 가지 였습니다.

• 정렬 기준
  • 해당 문제 접하게 된다면 강연 기한을 기준으로 정렬해야 할지 강연료를 기준으로 해야할지 고민하게 됩니다.
  • 하지만 아래와 같은 테스트 케이스가 주어졌을 때 강연료를 기준으로 정렬해야된다는 걸 알 수 있습니다.
    
    • wrong : 1days -> 10, 2days -> 20
    • answer : 1days -> 20, 2days -> 20

3
10 1
20 2
20 2

wrong : 30 
answer : 40

• 강연 선정 기준
  • 날짜를 1씩 증가하며 높은 강연료를 주는 강의를 선정할 수도 있습니다. 하지만 그렇게 되는 경우도 마찬가지로  아래와 같은 테스트 케이스에서 문제가 됩니다.
    • wrong : 1days -> 30, 2days -> 20, 3days -> x 
    • answer : 1days -> 10, 2days -> 20, 3days->30
  • 때문에 각 강연들은 최대한 기한에 가깝게 설정해주어 취할 수 있는 이득은 모두 취할 수 있도록 주의해야합니다.

3
10 1
20 2
30 4

wrong : 50
answer : 60

 

코드

---

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

public class Main_2109_순회강연 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int N = Integer.parseInt(br.readLine()); // 강연 요청 수
		
		Queue<int[]> queue = new PriorityQueue<>((o1, o2) -> {
			if(o1[0] == o2[0]) return Integer.compare(o1[1], o2[1]); // limit는 오름차순
			return Integer.compare(o2[0], o1[0]); // pay는 내림차순
		});
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int pay = Integer.parseInt(st.nextToken()); // 강연료
			int timeLimit = Integer.parseInt(st.nextToken()); // 기한
			
			queue.add(new int[] {pay, timeLimit});
		}
		
		boolean[] schedule = new boolean[10001]; // 스케쥴 체크
		int answer = 0; // 최대로 벌 수 있는 금액
		while(!queue.isEmpty()) {
			int[] cur = queue.poll();
			
			int time = cur[1];
			while(time > 0) { // 각 강연은 최대한 마지막 기한에 할 수 있도록 함
				if(!schedule[time]) {
					schedule[time] = true;
					break;
				}
				else time--;
			}
			if(time > 0)answer += cur[0]; // 강연을 할 수 있다면 합
		}
		System.out.println(answer);
	}
}