[Leetcode] 1402. Reducing Dishes

문제 : https://leetcode.com/problems/reducing-dishes/description/

---

n개의 요리의 만족도가 있고 어떤 요리든 1단위 시간 안에 조리할 수 있습니다.

한 요리의 "Like-time coefficient"은 "해당 요리와 이전 요리를 모두 조리하는데 걸리는 시간 x 해당 요리의 만족도"(time[i] * satisfaction[i]) 입니다.

요리는 어떤 순서로든 준비할 수 있고, 일부 요리를 버릴 수도 있습니다.

가능한 Like-time coefficient의 최대값은 얼마입니까.

---

만족도는 음수가 가능합니다. time[i]는 양수이기 때문에 모든 음수 만족도를 제거하는게 최대값을 만드는 것이라 생각될 수 있지만,

 다음과 같은 경우는 다릅니다.

 

satisfaction = [-1, 2, 10]

만족도를 제거하지 않은 경우 : 1 * -1 + 2 * 2 + 3 * 10 = 33.

음수 만족도를 제거한 경우 : 1 * 2 + 2 * 10 = 22.

 

즉, 음수만족도를 제거하는게 항상 최대값을 만들 수 없음을 보여줍니다.

요리의 만족도가 클수록 뒤에 조리할수록 큰 like-time coefficient를 구할 수 있습니다.

따라서 먼저 satisfaction을 오름차순 정렬한 뒤, 앞에서부터 만족도를 제거해나가면서 like-time coefficient를 구했을 때 최대값이 정답이 됩니다.

 

시간복잡도는 O(N^2).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/1402.%20Reducing%20Dishes.cpp