Microwaving Lunch Boxes

문제: LUNCHBOX / 그리디(탐욕적인 방법)

[해결책 / 후기]

 

힌트 - 먹는 시간이 오래 걸리는 사람을 먼저 처리한다.

 

입력이 A, B, C, D 네명에 대하여 다음과 같을 때

 

M: 4 2 6 1 

E: 5 2 2 1

 

아래와 같이 시간 흐름을 그려보니 문제가 좀 명확해졌다. (총 14분의 시간이 걸림)

 

빨간 숫자는 식사가 끝나는 시간을 나타낸다.

 

 

1) 먹는 시간이 오래걸리는 사람 기준으로 내림차순으로 정렬하고 

2) 전자렌지가 사용가능한 시점을 기준으로 시간을 측정하였다.

코드: https://github.com/xgate/algospot/blob/master/GREEDY/LUNCHBOX.cpp

[출처] [AOJ 문제] Microwaving Lunch Boxes|작성자 DevMoon