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

출력

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

예제 입력 1 

7

20 1

2 1

10 3

100 2

8 2

5 20

50 10

예제 출력 1 

185

접근방법

해당 문제의 시간제한은 2초이며, 경우의수( N)은 10,000까지로 시간복잡도 O(N²) 까지 가능하다.

 

어떤 경우든 P(강의료) 가 적은 강의를 많은 하는것보다는  P(강의료)가 큰 경우를 많이 하는것이 좋다.

이 전제를 가지고 아래와 같이 차례로 진행해보겠다.

 

1) P(강의료)가 큰 경우로 정렬을 해준다. 

-> P(강의료)가 같은 경우에는 D(기간)로 정렬해준다.

 

2) P(강의료)가 큰 경우로 가능한 많이 할 수 있는 경우를 찾는다

2 (N값)
100(P) 2(D)
300(P) 1(D)

이렇게 입력이 주어졌을때 최대로 벌 수 있는 경우를 생각해보면
첫쨋날에 300(P) 를 벌고 둘쨋날에 100(P)를 버는것이 최고인 경우이다.

 

이 부분을 활용해서 입력된 D의 최대값을 크기로 하는 Visited 라는 배열을 선언해준다.

해당 배열에는 강의를 했는지 안했는지를 표시해준다.  아래와 같이 입력됐다고 했을때

3
200 2
100 1
300 3

날짜 (Visited 인덱스 번호+1)	1	2	3
값	100	200	300

위의 테이블처럼 300 3일은 3일안에 언제든지 가능하다 하지만 100 1은 무조건 1일 안으로만 강의를 할 수 있기 때문에  visited 배열에 입력 우선순위는 D가 낮은 순으로 높게 주어야 한다.  

이제 코드로 표현해보겠다.

 

 

코드

package Greedy;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

public class BJ_2109 {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int n = scan.nextInt();
		List<int[]> list = new ArrayList<int[]>();
		
		//p,d 값 입력
		while(n-- > 0) {
			int[] pdValue = new int[2];
			pdValue[0] = scan.nextInt();
			pdValue[1] = scan.nextInt();
			list.add(pdValue);
		}
		
		//d 기준으로 정렬, 만약 d가 같다면 p기준으로 정렬
		Collections.sort(list,new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				if(o1[0]==o2[0]) {
					return o2[1]-o1[1];
				}
				return o2[0]-o1[0];
			}
		});
		
		long result = 0;
		int maxDay = findMaxDay(list);
		boolean[] visited = new boolean[maxDay];
		
		for(int[] temp : list) {
			if(!visited[temp[1]-1]) {
				visited[temp[1]-1]=true;
				result+=temp[0];
			}
			else {
				for(int i=temp[1]-1;i>=0;i--) {
					if(!visited[i]) {
						visited[i]=true;
						result+=temp[0];
						break;
					}
				}
			}
		}
		System.out.println(result);
	}
	

	public static int findMaxDay(List<int[]> list) {
		int max = 0;
		for(int[] temp : list) {
			max = Math.max(temp[1], max);
		}
		return max;
	}
}