링크

순회강연-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만큼의 강연료를 지불한다라고 읽고 문제를 처음부터 잘못 접근하였다;;;;
후 다음부턴 꼼꼼하게 읽자!!

1. 우선순위 큐안에 제네릭 타입을 int배열로 잡아준다.
2. 최대의 p값을 가져와야 하기에 비용 기준으로 내림차순 정렬
3. 비용이 같으면 d를 내림차순으로 정렬(d일 안에 해야 하는 것이기 때문)
4. boolean배열 값을 잡아준다.(강연을 했다는 것을 표시하기 위해)
5. 다음 이중for문 안쪽 for문은 day부터 줄여나가면서 방문을 하지 않은 날짜에 true값을 설정해주고 result값을 더해나간다.

Code

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

public class Main {
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int n=Integer.parseInt(br.readLine());
		boolean check[]=new boolean[10001];
		int result=0;
		
		if(n==0)
		{
			System.out.println(0);
			return ;
		}
		PriorityQueue<int[]> pq=new PriorityQueue<int[]>
		(new Comparator<int[]>() {
			public int compare(int[] o1, int[] o2)
			{
				if(o1[0] < o2[0])
					return 1;
				
				else if(o1[0]==o2[0])
					return o2[1]-o1[1];
				
				return -1;
			} 
		});
		
		for(int i=0; i<n; i++)
		{
			StringTokenizer st=new StringTokenizer(br.readLine());
			int num1=Integer.parseInt(st.nextToken());
			int num2=Integer.parseInt(st.nextToken());
			pq.add(new int[] {num1, num2});
		}
		
		for(int i=0; i<n; i++)
		{
			int arr[]=pq.poll();
			int price=arr[0];
			int day=arr[1];
			
			for(int j=day; j>=1; j--)
			{
				if(!check[j])
				{
					check[j]=true;
					result+=price;
					break;
				}
			}
		}
		
		System.out.println(result);
		
	}
}