문제 풀이

예를들어 강연의 데드라인이 2일이라면 굳이 1일에 강연을 할 필요가없다. 1일에 하든 2일에 하든 강연을 하면된다.
그렇다면 가장 늦은날짜에 강연을 할 수 있고 페이가 높은 강연부터 강연을하면된다.
그러면 가장 늦은 날짜인 10000일부터 시작해서 현재 진행할 수 있는 강연을 넣어준다.
예제
7
20 1
2 1
10 3
100 2
8 2
5 20
50 10
에서는
20일에는 5의 페이를 받으면서 강연을 할 수 있다.
10일에서는 50의 페이를 받으면서 강연을 할 수 있다.
3일에서는 10의 페이를 받으면서 강연을 할 수 있다.
2일에서는 100, 8중 100의 페이를 받으면서 강연을 할 수 있다.
1일에서는 강연을 할 수있는 후보는 2일에 못한 페이 8의 강연과 데드라인이 1인 페이 20, 2의 강연이다.

그 중 가장 페이가 높은 20의 강연을 선택하면된다.

다른 예로
3
2 1
9 2
10 2
일 경우

2일에는 페이 10의 강연을 하면된다.
1일에는 데드라인이 2일인 페이 9의 강연과 데드라인이 1일인 페이 2의강연 중 페이 9인 강연을 하면된다.

문제 링크

boj/2109

소스코드

PS/2109.java

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;


public class Main {


  static int []p= new int [10001];
  static int []d= new int [10001];
  static Vector<Integer> []v = new Vector[10001];
  static boolean []visit= new boolean[10001];
  static int n;

  static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
  static class Pair implements Comparable<Pair>
  {
      public int a,b;
      public Pair(int a, int b)
      {
          this.a=a;
          this.b=b;
      }
      @Override
      public int compareTo(Pair target) {
         if(a == target.a)
         {
             return b > target.b? 1:-1;
         }
         else
             return a > target.a?1:-1;
      }
  }
  public static void main(String[] args) throws IOException {

      n = Integer.parseInt(br.readLine());
      PriorityQueue<Pair> pq = new PriorityQueue<>();
      for(int i=1;i<=10000;i++)
        v[i] = new Vector<Integer>();
      for(int i=0;i<n;i++)
      {
          StringTokenizer st = new StringTokenizer(br.readLine());
          p[i] = Integer.parseInt(st.nextToken());
          d[i] = Integer.parseInt(st.nextToken());

          v[d[i]].add(p[i]);
      }

      int ans = 0;
      for(int i=1;i<=10000;i++)
      Collections.sort(v[i],Collections.reverseOrder());
      for(int i=10000;i>=1;--i)
      {
          if(!visit[i]) {
              visit[i] = true;
              for (int j = 0; j < v[i].size(); j++) {
                  pq.add(new Pair(-v[i].get(j).intValue(), i));
              }
              if(pq.isEmpty())
                  continue;

              int pay = pq.peek().a;
              int day = pq.peek().b;
              ans+= -pay;
              pq.poll();
          }

      }
      bw.write(Integer.toString(ans));
      bw.flush();

  }

}