[백준] 순회 공연 - JAVA

문제

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

풀이

강연들을 d를 기준으로 내림차순 정렬 해준다. 예를들어 다음과 같은 강연이 입력으로 들어오고 d를 기준으로 내림차순을 해준다면 다음과 같다.
50 2
70 2
60 1
이제 어떠한 날에 어떤 강연을 선택할지 찾으면 된다.

먼저 1일 부터 어떤 강연을 할지 찾는다고 하자 그렇다면 강연료가 제일 비싼 70 2 강연을 1일에 선택하게 될것이다.
그다음 2일에 강연을 선택해야하는데 2일에는 강연기한이 1일인 강연을 선택하지 못하게 되고 그로인해 2일에는 50 2인 강연을 선택하게 된다.

2일에 70 2인 강연을 선택하고 1일에 60 1인 강연을 선택하는게 최적의 답이지만 지금 한 방법은 최적의 답이 나오지 않게 된다.

그렇다면 어떻게 하면 최댓값을 구할 수 있을까??

1일부터 강연을 선택하지말고 강연기한중 제일 긴 기한부터 강연을 선택하면된다.
위 강연들중 2일이 젤 긴 기한이므로 2일부터 강연을 선택하면 70 2를 선택하게 된다. 이제 1일에 선택할 강연은 60 1 강연이 되게 된다.

그렇다면 다음과 같은 상황에서는 어떻게 해야 할까??
70 2
60 2
50 1
2일에 첫번째 강연을 선택하게 되고 1일에 2번째 강연을 선택하면 된다.
이를 구현하기 위해 우선순위 큐를 사용하였다. 강연을 선택할 날짜와 강연 기한을 비교하여 해당 날짜에 강연을 할 수 있는지 판단후 할 수 있다면 우선순위 큐에 강연료를 넣어주고 다 넣었다면 우선순위 큐에서 Dequeue를 하여 answer변수에 더해주었다.

즉 2일에 할 수 있는 강연을 모두 찾은 후 (첫번째,두번째 강연)
큐에 넣어주고 (70,60) -> 강의료가 큰 값이 우선순위가 높게 설정
다 넣었다면 dequeue를 한번 해준 후 (70) 그값을 answer에 더해주었다
(answer += 70)

그다음 1일에 할 수 있는 강연을 모두 찾은 후 (세번째 강연)
큐에 넣어주고 (60,50)
다 넣었다면 dequeue를 한번 해준 후 (60) 그값을 answer에 더해주었다
(answer += 60)

이것을 현재 날짜가 1일때까지 반복해주면 최종답이 나오게 된다.

최종 코드

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

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken());
    Lecture[] lectures = new Lecture[n];
    for(int i=0; i<n; i++) {
      st = new StringTokenizer(br.readLine());
      lectures[i] = new Lecture(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
    }
    Arrays.sort(lectures);
    PriorityQueue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());
    int answer = 0;
    int j=0;
    if(lectures.length >= 1) {
      for(int i = lectures[0].d; i >=1; i--) {
        // 해당날에 강연을 할 수 있는지
        // 해당날 보다 d값이 크거나 같을때 강연 가능
        while(j < n && i <= lectures[j].d) {
          q.offer(lectures[j].p);
          j++;
        }
  
        if(!q.isEmpty()) {
          answer += q.poll();
        }
      }
    }
    System.out.println(answer);
  }
  public static class Lecture implements Comparable<Lecture>{
    int p,d;
    Lecture(int p, int d) {
      this.p = p;
      this.d = d;
    }
    @Override
    public int compareTo(Lecture o) {
      return o.d - this.d;
    }
  }
}