본문 바로가기
알고리즘 문제/Algospot

[algospot][LUNCHBOX] Microwaving Lunch Boxes

by 햄과함께 2019. 7. 13.
320x100

문제 : https://algospot.com/judge/problem/read/LUNCHBOX


그리디하면 나오는 단골 문제.

전자레인지에 돌리는 행동은 선형적이지만 먹는 것은 병렬적으로 처리할 수 있다.

따라서 시간을 효율적으로 사용하려면 중요한 건 먹는 시간이다. 

병렬적으로 처리된다고 했을 때 가장 먼저 시작되어야 하는 것은 시간이 가장 오래 걸리는 것이다.

따라서 도시락을 먹는 시간의 내림차순으로 정렬하고 이 때 모든 도시락을 데우고 먹는 데 걸리는 시간(1)을 구하면 이 결과가 정답이 된다.

(1)을 구하는 방법은 도시락을 정렬한 뒤 앞에서부터 탐색하면서 데우는 시간과 먹는 시간을 누적해간다.

데우는 시간은 선형적이므로 각 도시락의 데우는 시간의 합이다.

누적된 먹는 시간은 도시락을 데울 때 그 시간만큼 소요되고(-), 탐색 중인 도시락의 먹는 시간과 현재 누적된 도시락의 먹는 시간 중 최대값이다. 

시간 복잡도는 도시락의 정렬 시간(O(NlogN)) + 정렬된 도시락의 탐색 시간(O(N)) 이므로 O(NlogN)이 된다.


소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/algospot/LUNCHBOX.cpp

 

fpdjsns/Algorithm

알고리즘 정리. Contribute to fpdjsns/Algorithm development by creating an account on GitHub.

github.com

 

320x100

댓글