알고리즘 문제해결 전략 Chapter 10 - LUNCHBOX(C++)

포타토·2020년 2월 5일
0

알고리즘

목록 보기
40/76

예제: 도시락 데우기

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 2^31.

예제 입력

2
3
2 2 2
2 2 2
3
1 2 3
1 2 1

예제 출력

8
7

풀이

와... 내가 이 지문을 그대로 접했다면 풀 수 있었을까 생각을 해본다. Ainu7은 대체 뭐냐고..😬
알고리즘 문제해결은 친절한 도서였다. 이걸 한글로 번역해서 써놓다니.

각설하고, 이 문제를 처음 받았을 때 곰곰이 생각했다. 도시락을 데우는 시간은 상관 없이 먹는 시간만 고려하면 될 것 같은데? 간단해 보여서 풀기가 무서웠다. 필자가 모르는 함정이 있을까봐.. 그러나 이것이 바로 탐욕법이였다!

탐욕법은 풀이도 중요하지만, 내가 세운 논리가 맞는지, 탐욕법을 적용할 수 있는지 판단하는 것이 중요한 것 같다.

이 문제는, 결국 도시락을 먹는 시간을 내림차순으로 정렬하여, 도시락을 다 먹는 시간을 계산하면 된다.

여러가지 방법이 있겠지만, 필자는 도시락을 데우는 총 시간 + 도시락을 다 데우고 나서 남은 도시락을 먹는 시간의 최대값 으로 구했다. 후술하겠지만, 도서 풀이는 좀 더 직관적으로 풀고있다.

전체적인 소스코드는 아래와 같다.

소스 코드

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int n;
vector<int> heatTime, eatingTime;

bool compare(pair<int, int> p1, pair<int, int> p2) {
	if (p1.first > p2.first) return true;
	else if (p1.first == p2.first && p2.second > p2.second) return true;
	return false;
}

int getTime() {
	vector<pair<int, int>> time(n);
	for (int i = 0; i < n; i++) {
		time[i] = make_pair(eatingTime[i], heatTime[i]);
	}

	//sort(time.begin(), time.end(), greater<pair<int, int>>());
	sort(time.begin(), time.end(), compare);

	int res = 0, restEat = 0;
	for (int i = 0; i < n; i++) {
		res += time[i].second;	//도시락 데우는 시간 더해줌
		//데우고 나면 먹음
		restEat = max(restEat - time[i].second, time[i].first);
	}

	return res + restEat;
}

int main() {

	int testCase;
	cin >> testCase;

	for (int tc = 0; tc < testCase; tc++) {
		cin >> n;
		heatTime = eatingTime = vector<int>(n);

		for (int i = 0; i < n; i++) {
			cin >> heatTime[i];
		}
		for (int i = 0; i < n; i++) {
			cin >> eatingTime[i];
		}

		cout << getTime() << endl;
	}

	return 0;
}

풀이 후기

앞서 말했듯이, 도서 풀이는 도시락을 데우는데 걸린 시간(누적) + 도시락을 먹는데 남은 시간의 최대값을 구한다. 필자가 보기에는 꼭 도서 풀이라서가 아니라, 필자의 풀이보다 좀 더 직관적인 것 같다.(시간차이는 내꺼가 좀 더 빨랐다구😗)
항상 느끼는거지만, 사람이 100명있다면 100개의 다른 코딩이 나오는 것 같다. 성격이 묻어나오는걸까? 어쩌면 코딩하는 스타일을 보고 성격을 판단해 합풀을 판단하는 면접 방법도 언젠가 나올지 모르겠다.

profile
개발자 성장일기

0개의 댓글