C언어 ] leetCode 1402 - Reducing Dishes

 

 

 

leetCode 1402 문제

 

A chef has collected data on the satisfaction level of his n dishes. Chef can cook any dish in 1 unit of time. Like-time coefficient of a dish is defined as the time taken to cook that dish including previous dishes multiplied by its satisfaction level i.e. time[i] * satisfaction[i]. 

Return the maximum sum of like-time coefficient that the chef can obtain after preparing some amount of dishes. Dishes can be prepared in any order and the chef can discard some dishes to get this maximum value.

 

 

Example 1: 

• Input: satisfaction = [-1,-8,0,5,-9] 
• Output: 14 
• Explanation: After Removing the second and last dish, the maximum total like-time coefficient will be equal to (-1*1 + 0*2 + 5*3 = 14). Each dish is prepared in one unit of time.

 

Example 2:

• Input: satisfaction = [4,3,2] 
• Output: 20 
• Explanation: Dishes can be prepared in any order, (2*1 + 3*2 + 4*3 = 20)

 

Example 3:

• Input: satisfaction = [-1,-4,-5] 
• Output: 0 
• Explanation: People do not like the dishes. No dish is prepared.

 

Constraints: 

• n == satisfaction.length 
• 1 <= n <= 500 
• -1000 <= satisfaction[i] <= 1000

 

이전에 푼 것과 비슷한 계열의 문제다. 문제보고 뭔소리야 했는데 예시를 보니까 이해갔다.

 

요리사는 Like-time coefficient라는걸 최대화하기 위해 0개에서 satisfactionSize개 사이의 요리를 취사선택해 제출할 수 있다. 

 

Like-time coefficient는 time[i] * satisfaction[i] 의 총합인데 아무것도 제출 안했을 때는 0이고, 여기서 time은 쉽게 생각하면 첫 제출시 1이고 그 뒤로는 1씩 증가하는 계수이다.

 

음수는 버리고 양수만 제출하면 되는거 아니야? 할 수 있는데 그렇지 않다. 예시 1을 보면 요소 5만 제출하면 (5*1 = 5)인데 요소 -1, 0, 5를 제출하면 (-1*1 + 0*2 + 5*3 = 14)가되서 satisfaction이 더 커진다.

 

나는 먼저 qsort로 배열을 오름차순 정렬해놓고 satisfactionSize개의 경우의 수를 다 확인해서 max가 되는 값을 찾았다.

 

 

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int maxSatisfaction(int* satisfaction, int satisfactionSize) {
    int max = 0;
    qsort(satisfaction, satisfactionSize, sizeof(int), compare);
    for(int i = 0; i < satisfactionSize; i++) {
        int sum = 0;
        for(int j = i, coff = 1; j < satisfactionSize; j++, coff++) {
            sum += coff * satisfaction[j];
        }
        max = sum > max ? sum : max;
    }
    return max;
}