leetcode 1402 - Reducing Dishes

https://leetcode.com/problems/reducing-dishes/submissions/

풀이

몇 개의 접시를 없애야 한다면 어떤 접시를 없애는 것이 좋을지 생각해보자. 당연히 satisfaction이 낮은 접시를 우선 없애는 것이 최선이다.

없앤다면 satisfaction이 낮은 접시 n개를 없애는 게 최선이고, 이다음 남은 접시의 순서를 찾는 방법은 더 쉽다. 뒤로 갈수록 가중치가 크기 때문에 오름차순으로 정렬을 하면 된다.

 

다시 정리해보면, 먼저 접시를 정렬한 후 앞에서부터 한 개씩 없애보면서 최고 높은 satisfaction 값을 찾으면 답이 된다.

$[a_1, a_2, a_3, ...., a_n]$으로 정렬을 했을 때 가능한 정답은 다음 중에 있다.

• 0개 없앤 경우: $a_1 + 2a_2 + 3a_3 + ... + na_n$
• 1개 없앤 경우: $a_2 + 2a_3 + 3a_4 + ... + (n-1)a_n$
• 2개 없앤 경우: $a_3 + 2a_4 + 3a_5 + ... + (n-2)a_n$
• ...
• n-2개 없앤 경우: $a_{n-1} + 2a_n$
• n-1개 없앤 경우: $a_n$
• n개 없앤 경우: $0$

 

n개를 없앤 경우부터 거꾸로 식을 다시 써보면 다음과 같다.

• $c_0 = 0$
• $c_1 = a_n$
• $c_2 = a_n + (a_{n-1} + a_n) = c1 + \sum_{i=n-1}^{n} a_i$
• $c_3 = a_n + (a_{n-1} + a_n) + (a_{n-2} + a_{n-1} + a_n) = c2 + \sum_{i=n-2}^{n} a_i$
• ...

 

즉 모든 k에 대해 $c_k = c_{k-1} + \sum_{i=n-k+1}^{n} a_i$ 의 최댓값을 구하면 된다.

$\sum$은 매번 할 필요 없이 누적하며 한 번에 계산할 수 있으므로 총 시간 복잡도는 $O(n)$이다.

 

 

코드

class Solution {
public:
    int maxSatisfaction(vector<int>& satisfaction) {
        sort(satisfaction.begin(), satisfaction.end());
        int ans = 0, c = 0, sum = 0;
        for(int i = satisfaction.size() - 1; i >= 0; i--) {
            sum += satisfaction[i];
            c += sum;
            ans = max(ans, c);
        }
        
        return ans;
    }
};