문제
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.
예제 입력
2
3
2 2 2
2 2 2
3
1 2 3
1 2 1
예제 출력
8
7
Concept
결정적으로 중요한 것은 데우는 시간이다. 도시락을 먹는 것은 동시에 다수가 할 수 있지만, 데우는 것은 반드시 하나씩 해야 하기 때문이다.
데우는 시간을 기준으로 도표를 그려보면 먹는 시간을 내림 차순으로 정렬하는 것이 가장 이상적인 경우임을 알 수 있다. 먹는 시간이 가장 많이 필요한 사람을 최대한 먼저 먹게 하는 것이 점심시간을 최소로 할 수 있기 때문이다. 이와 같이 탐욕법을 이용하는 것이 가장 간단한 해결책이 될 것이다. 여기에 몇가지 사항만 유의하며 양념질만 좀 해주면 된다.
Code
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//n행 2열 벡터에서 2열을 기준으로 내림차순 정렬을 위한 함수
bool SortSecCol(const vector<int>& v1, const vector<int>& v2) {
return v1[1] > v2[1];
}
int main() {
int c;
cin >> c;
for (int i = 0; i < c; i++) {
int n;
cin >> n;
vector<vector<int>> arr(n, vector<int>(2, 0));
for (int j = 0; j < n; j++) {
cin >> arr[j][0];
}
for (int j = 0; j < n; j++) {
cin >> arr[j][1];
}
//2열을 기준으로 내림차순 정렬 진행.
sort(arr.begin(), arr.end(), SortSecCol);
int sumWarming = 0;
int ret = -1;
for (int j = 0; j < n; j++) {
//초기 조건 설정
if (j == 0) {
ret = arr[j][0] + arr[j][1];
sumWarming += arr[j][0];
}
else {
// n-1번째 사람의 먹는 시간이 극단적으로 오래 걸리고,
// n번째 사람의 데우는 시간과 먹는 시간이 짧을 경우까지 고려
ret = max(ret, sumWarming + arr[j][0] + arr[j][1]);
sumWarming += arr[j][0];
}
}
cout << ret << endl;
}
}Comment
그리디 알고리즘이 필요한 이유. 몇 가지 예외적인 사항만 잘 고려하면 매우 간단히 코드 작성이 가능하다.
