알고스팟: 도시락 데우기 (ID: LUNCHBOX)

[문제 링크]

algospot.com :: LUNCHBOX

---

먹는데 가장 오래걸리는 도시락을 먼저 데우고 먹기 시작해야 가장 빨리 점심시간을 마칠 수 있다.

따라서, 먹는데 걸리는 시간을 기준으로 내림차순 정렬한 다음 오래 걸리는 도시락 순으로 데우도록 구현하였다.

---

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<pair<int, int>> lunchBox;

int Greedy(int N)
{
	// 먹는데 오래걸리는 순으로 정렬
	sort(lunchBox.begin(), lunchBox.end(), greater<pair<int, int>>());

	int longest = 0, time = 0;

	for (int i = 0; i < N; i++)
	{
		if (longest < lunchBox[i].first + lunchBox[i].second)
		{
			longest = lunchBox[i].first;
			time += lunchBox[i].second;
		}
		else
		{
			longest -= lunchBox[i].second;
			time += lunchBox[i].second;
		}
	}

	return time + longest;
}

int main(void)
{
	int tc;
	cin >> tc;
	while (tc--)
	{
		int N;
		cin >> N;

		int heat[10000];
		for (int i = 0; i < N; i++)
			cin >> heat[i];

		int eat[10000];
		for (int i = 0; i < N; i++)
			cin >> eat[i];

		for (int i = 0; i < N; i++)
			lunchBox.push_back(make_pair(eat[i], heat[i]));

		cout << Greedy(N) << endl;

		lunchBox.clear();
	}

	return 0;
}

알고리즘 200일 프로젝트 - 108 day