문제

출처 : https://www.algospot.com/judge/problem/read/LUNCHBOX

After suffering from the deficit in summer camp, Ainu7 decided to supply lunch boxes instead of eating outside for Algospot.com winter camp.

He contacted the famous packed lunch company “Doosot” to prepare N lunch boxes for N participants. Due to the massive amount of order, Doosot was not able to prepare the same menu. Instead, they provided different N lunch boxes. Ainu7 put all the lunch boxes to a refrigerator.

The lunch time has come, and suddenly Ainu7 noticed that there is only one microwave available. As all lunch boxes are not the same, they need a different amount of time to microwave and eat. Specifically, i-th lunch box needs Mi seconds to microwave and Ei seconds to eat.

Ainu7 needs to schedule microwave usage order to minimize lunch time. Lunch time is defined as the duration from the beginning of microwaving of any lunch box to the end of eating for all participants. Write a computer program that finds minimum lunch time to help Ainu7. Note that substituting lunch while microwave is turned on is totally unnecessary, because the lunch will be cooled down.

입력

The first line of the input contains one integer T, the number of test cases.

Each test case consists of three lines. The first line of each test case contains N(1≤N≤10000), the number of the participants.

N integers will follow on the second line. They represent M1, M2, ⋯, MN. Similarly, N integers will follow on the third line, representing E1, E2, ⋯, EN.

출력

For each test case, print the minimized lunch time in one line. It is guaranteed that the answer is always strictly less than 231.

풀이

탐욕법, 또는 그리디 알고리즘은 정답을 도출하는 각 단계마다 가장 좋은 답을 선택하는 알고리즘으로, 이를 적용할 수 있는 특수한 상황에서 보다 빠르고 효율적인 계산을 수행하기 위한 알고리즘이다. 탐욕적 알고리즘을 문제에 적용하여 풀기 위해서는 두 가지의 속성, 탐욕적 선택 속성과 최적 부분 구조를 증명하여야 한다. 탐욕적 선택 속성은 각 단계에서 선택한 답을 포함하는 최적해가 존재함을 보이는 것이고, 최적 부분 구조는 각 단계에서 항상 최적의 선택만을 했을 때 전체 최적해를 구할 수 있는지 여부를 증명하는 것이다.

이 문제의 경우, 어림잡아 먹는데 오래 걸리는 순서대로 식사를 할 경우 걸리는 시간이 최소화될 수 있음을 짐작할 수 있다. 먼저, 각 사람들마다 다 먹는데 걸리는 시간은 (시작부터 자신까지 음식을 데우는 시간의 합) + (먹는 시간)이 된다. 이 때, 모든 사람들이 식사를 마쳐야 끝난 것이므로 끝날때까지 걸리는 시간은 사람들마다 먹는데 걸리는 시간 중 최댓값이 된다. 즉, 각 사람들마다 다 먹기까지 걸리는 시간의 최댓값을 최소화하는 방향으로 접근해야 하는데, 여기서 먹는데 오래 걸리는 사람순으로 먹는다고 가정하여 접근한다.

처음이 아닌 특정 순서에서 먹는데 가장 오래 걸리는 도시락이 위치한다는 최적해를 가정하였을 때, 뒷 사람들의 걸리는 시간은 데우는데 걸리는 시간에만 영향을 받으므로 고려하지 않아도 된다. 즉, 처음부터 가장 오래걸리는 도시락을 먹는 사람까지의 시간들 중에서 최댓값을 고려할 때, 오래걸리는 도시락을 먹는 사람은 어떠한 경우에도 모든 데우는 시간을 기다려야 하므로 이 때의 다 먹는 시간이 최댓값이 되므로, 순서를 바꾸는 어떠한 경우에도 해당 값보다 클 수 없으므로 오래 걸리는 도시락을 제일 먼저 먹도록 바꾼다해도 최적해가 성립한다.

나머지 도시락들에 대해서도 걸리는 최대시간이 최소화되는 방향으로 계산되기 때문에 각 단계에서 최적해를 선택하여도 상관없음을 알 수 있다. 따라서, 이 방법이 나타내는 탐욕법으로 접근할 때 탐욕적 선택속성과 최적 부분구조를 만족한다고 볼 수 있다.

//Pair(int hot, int eat)
	Vector<Pair> v = new Vector<Pair>();
	for (int j = 0; j < n; j++) {
		v.add(new Pair(A[j], B[j]));
	}
// 데우는데 오래 걸리는 순으로 정렬
	Collections.sort(v, new PairComparator());
	int max = 0;
	int sum = 0;
	for (int j = 0; j < n; j++) {
		Pair p = v.get(j);
		sum += p.hot;
		max = Math.max(max, sum + p.eat);
	}
	System.out.println(max);

각 도시락을 데우는데 걸리는 시간과 먹는데 걸리는 시간을 저장할 때, 걸리는 시간 순서로 내림차순으로 정렬하여, 각각의 사람이 다 먹는데 걸리는 시간들 중 최댓값을 골라 답을 찾을 수 있다.