[C++] 알고스팟/탐욕법 - Microwaving Lunch Boxes

문제 링크

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

algospot.com :: LUNCHBOX

 

도시락을 먹는데 오래 걸리는 것 부터 진행을 하게되면 다음 도시락을 데우고 먹는 시간과 중복이 될 수 있기 때문에 시간을 줄일 수 있습니다.

 

위의 예시를 볼 때 첫 번째 도시락을 데우고 먹는데 11초가 걸립니다.

 

 

두 번째 도시락은 첫 번째 도시락을 데운 직후에 바로 데울 수 있기 때문에 6초만에 먹을 수 있습니다.

이는 첫 번째 도시락보다 두 번째 도시락을 먹는데 더 짧은 시간이 걸립니다.

세 번째도 마찬가지로 두 번째 도시락을 데운 직후에 바로 데운 후 먹으면 9초가 걸립니다.

여전히 첫 번째 도시락보다 빠른 시간이기 때문에 첫 번째 도시락이 다 비워지기만을 기다리면 됩니다. 

 

하지만 먹는데 오래 걸리는 도시락을 위와 같이 가장 마지막에 배치시키면

이전의 모든 도시락을 다 데우는걸 기다린 후 마지막 도시락을 데우고 먹는데 총 17초가 걸리기 때문에 최소 시간이 될 수 없습니다.

 

 

구현 코드