algospot 도시락 데우기 (문제 ID: LUNCHBOX) c++

알고스팟 문제 링크: https://www.algospot.com/judge/problem/read/LUNCHBOX

algospot.com :: LUNCHBOX

도시락의 갯수와 각 도시락마다 데우는시간, 먹는 시간을 입력으로 주어지고, 한번에 하나의 도시락을 데울 수 있으며 데운 도시락은 기다리지 않고 바로 먹는다고 했을 때, 필요한 총 식사시간을 구하는 문제이다.

모든 도시락은 무조건 1번씩 다 데워져야 되기 때문에 데우는 시간은 똑같다.

문제는 먹는시간인데 먹는시간이 오래걸리는 순서대로 데워서 바로 먹는 그리디 알고리즘을 이용하면 문제를 해결할 수 있다. 

정당성 증명으로는 최적해중에 먹는 시간이 오래걸리는 도시락을 비교적 덜걸리는 도시락보다 더 늦게 먹는 경우가 있다고 가정하자. 이때 두 도시락의 데우는 순서를 바꾸면 최적해 이하의 시간이 걸린다. 따라서 먹는 시간이 오래걸리는 순서대로 데워서 먹는 그리디 알고리즘의 정당성이 성립한다.

부분 구조 증명 또한 첫번째 도시락을 정했을 때, 나머지 도시락들에 대한 시간도 최소화 해야하므로 성립한다.

 

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/10.%20Greedy/LUNCHBOX.cpp

GitHub - sbl133/JongmanBook

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략1