문제 - 도시락 데우기

문제

-어느 순서로 도시락을 데워야 가장 빨리 점심시간을 마칠 수 있나?

 

예제 입력

2 //testcase
3 //도시락 수
2 2 2 //데우는데 걸리는 시간
2 2 2 //먹는데 걸리는 시간
3
1 2 3 
1 2 1

예제 출력

8
7

 

중요한 개념

-모든 도시락을 먹는데 같은 시간 C가 걸릴경우 , 어떤 순서로 도시락을 데우건 간에

점심 시간의 길이 = 모든 도시락을 데우는 시간 + 도시락 하나를 먹는 시간

*대신, 가장 먼저 데운 도시락이 마지막으로 데운 도시락을 먹고도 아직 먹고 있는 경우가 있음

(밑에 코드에서 max로 계산)

 

알고리즘 구상

-먹는 시간이 오래걸리는 순서대로 도시락을 데우기

 

코드

#include <iostream>
#include <fstream>
#include <vector>'
#include <algorithm>

int Heat(int boxNum, std::vector<int>& eat, std::vector<int>& cook)
{
	std::vector<std::pair<int,int>> order;
	for (int i = 0; i < boxNum; ++i)
	{
		//먹는데 걸리는 시간을 내림차순으로 편하게 정렬하기 위해 마이너스 붙여줌
		//이러면 가장 큰 수가 가장 작은수가 되고 오름차순 정렬했을 때 원래 가장 큰수가 맨 앞에옴
		order.push_back(std::make_pair(-eat[i],i));
	}
	std::sort(order.begin(), order.end());	

	int eatAndCookTimeSum = 0; 
	int beginEat = 0;
	for (int i = 0; i < boxNum; ++i)
	{
		int box = order[i].second;
		
		beginEat += cook[box];		
		//max(전 도시락까지 다 먹는데 걸리는 시간, 지금도시락을 요리하고 먹는데 까지 걸리는 시간) 비교
		eatAndCookTimeSum = std::max(eatAndCookTimeSum, beginEat + eat[box]);		
	}
	
	return eatAndCookTimeSum;
}

void Solution(std::ifstream& ifstream)
{
	int testcases=0;
	
	ifstream >> testcases;	
	
	for (int i = 0; i < testcases; ++i)
	{		
		int boxNum;
		ifstream >> boxNum;		

		std::vector<int> eat;
		std::vector<int> cook;
		for (int i = 0; i < boxNum; ++i)
		{			
			int tmp;
			ifstream >> tmp;			
			cook.push_back(tmp);
		}
		
		for (int i = 0; i < boxNum; ++i)
		{
			int tmp;
			ifstream >> tmp;			
			eat.push_back(tmp);
		}

		std::cout<<Heat(boxNum, eat, cook) << std::endl;
		
	}

}

int main(void)
{
	std::ifstream ifstream;
	ifstream.open("Input.txt");

	Solution(ifstream);
	return 0;
}

 

시간복잡도 : O(nlgn)

-처음에 모든 도시락을 먹는데 걸리는 시간의 역순으로 정렬하기 위한 시간