순회강연(백준 2109번),자바

2109번: 순회강연 (acmicpc.net)

2109번: 순회강연

 

 

import java.util.*;

public class Main {
	
	
	public static void main(String[] args)  {
		
		int n;
		int max=0;
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		ArrayList<Point> arr=new ArrayList<>();
		
		for(int i=0;i<n;i++) {
			int p=sc.nextInt(); int d=sc.nextInt();
			arr.add(new Point(p,d));
			max=Math.max(max, d);
		}
		
		Collections.sort(arr, new Comparator<Point>() {

			@Override
			public int compare(Point o1, Point o2) {
				
				if(o1.p==o2.p) return o1.d-o2.p;
				else return o2.p-o1.p;
			}
			
		});
		
		int[] dd=new int[max+1];
		
		for(int i=0;i<n;i++) {
			int p=arr.get(i).p;
			int d=arr.get(i).d;
			while(d>0 && dd[d]!=0) {
				d--;
			}
			if(d==0) continue;
			else dd[d]=p;
		}
		
		int answer=0;
		for(int i=1;i<=max;i++) answer+=dd[i];
		System.out.println(answer);
	}
	
	static class Point{
		int p;
		int d;
		public Point(int p, int d) {
			this.p=p;
			this.d=d;
		}
	}
}