Treejin's Note

문제 설명

• n개의 도시락이 있다.(1 <= n <= 10000)
• 도시락을 데우는데 쓰는 전자레인지는 1개 뿐이다.
• 도시락을 데우는 데는 m초, 먹는데는 e초가 걸린다.
• 도시락을 먹는 시간 : 첫 번째 도시락을 데우기 시작하는 순간 ~ 마지막 사람이 도시락을 다 먹을 때까지 걸리는 시간.

=> 도시락을 먹는데 걸리는 최소 시간을 출력하기

문제 풀이

도시락을 먹는 시간을 단축하기 위해서는

도시락을 먹는 시간은 데우는 시간 m, 먹는 시간 e로 이루어진다.

도시락은 한 번에 하나만 데울 수 있다. 모든 도시락을 데우고 다 먹어야 하므로 최소 sum(m)시간은 걸릴 것이다.

그렇다면, 도시락을 전부 데운 후(sum(m))에 먹기만 하는 시간을 최소화할 수 있는 방법으로 순서를 정해야 전체 시간을 단축시킬 수 있다.

이는 곧 마지막에 남는 e가 작아야 하므로, e가 큰 것부터 먼저 먹기 시작하는 것이 전체 시간을 최소화하는 방법이다.

문제 풀이 코드

#include <iostream>

using namespace std;

#define MAXVALUE 10000
#define MAX(a, b) (a > b ? a : b)

int lunchBox[MAXVALUE][2];
int sortedIndex[MAXVALUE];
int temp[MAXVALUE];

void mergeSort(int startIdx, int endIdx, int mid) {
	int i = startIdx;
	int j = mid + 1;
	int l = startIdx;

	while (i <= mid && j <= endIdx) {
		// e가 큰 것부터 앞에 배치
		if (lunchBox[sortedIndex[i]][1] > lunchBox[sortedIndex[j]][1])
			temp[l++] = sortedIndex[i++];
		else
			temp[l++] = sortedIndex[j++];
	}

	while (i <= mid)
		temp[l++] = sortedIndex[i++];
	while (j <= endIdx)
		temp[l++] = sortedIndex[j++];

	for (int l = startIdx; l <= endIdx; ++l)
		sortedIndex[l] = temp[l];
}

void sort(int startIdx, int endIdx) {	// 정렬
	if (startIdx >= endIdx) return;
	int mid = (startIdx + endIdx) / 2;

	sort(startIdx, mid);
	sort(mid + 1, endIdx);
	mergeSort(startIdx, endIdx, mid);
}

int main() {
	int C;
	cin >> C;
	for (int tc = 1; tc <= C; ++tc) {
		int n;
		cin >> n;
		for (int i = 0; i < 2; ++i) {
			for (int j = 0; j < n; ++j) {
				cin >> lunchBox[j][i];
			}
		}
		for (int j = 0; j < n; ++j) {
			sortedIndex[j] = j;
		}

		sort(0, n - 1);
		
		int chingTime = 0;	// 데우기 시작한 시간
		int endTime = 0;	// 다 먹은 시간
		for (int i = 0; i < n; ++i) {
			chingTime += lunchBox[sortedIndex[i]][0];
			endTime = MAX(endTime, chingTime + lunchBox[sortedIndex[i]][1]);
		}

		cout << endTime << endl;
	}
	return 0;
}