[Java] LeetCode 1402. Reducing Dishes

[Java] LeetCode 1402. Reducing Dishes

 

문   제 : 

n개의 만족도 배열 satisfaction 배열이 주어진다.

쉐프는 한 번에 하나씩의 요리를 할 수 있다.

요리를 할 때마다 Like-time의 계수가 1부터 +1씩 증가한다.

요리의 만족도는 Like-time의 계수 * satisfaction[i] 이다.

쉐프는 원하는 요리 (satisfaction[i])만 할 수 있다.

요리의 만족도를 가장 크게 만들면 몇 인가? 

 

 

Constraint

{ n == satisfaction.length }

{ 1 <= n <= 500 }

{ -1000 <= satisfaction[i] <= 1000 }

 

Matter

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 dishes preparation.

Dishes can be prepared in any order and the chef can discard some dishes to get this maximum value.

 

Example )

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.

=========================================================================

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

==========================================================================

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

 

 

---

접   근 : 

누적합을 이용한 DP

---

해    결  &  설    명: 

n개의 dp 배열을 선언해준다.

satisfaction 배열을 내림차순으로 정렬해준다. -> int 형태로 reverse 정렬을 못하기 때문에 Integer형으로 변환해서 내림차 정렬을 해준다.

변환한 Integer 배열 : sat[]

 

가장 큰 만족도를 가진 요리부터 요리 리스트에 추가한다.

요리를 할 때마다 계수가 +1이 되기 때문에 만족도가 양수이면 상승 할 것이고, 음수이면 반대로 하락 할 것이다.

이 점을 이용해 큰 만족도의 요리부터 요리를 시작한다.

 

요리가 1개일 경우부터, n개까지 경우를 생각한다.

1개 일 경우부터 dp 배열을 초기화 해준다. -> dp[0] = sat[i] * 1

요리가 늘어날 때마다 계수가 증가하기 때문에 dp 식을 구하기 위해 누적합을 구해준다.

 

dp[i] 구하는 방법 :

이때까지 한 요리들의 계수도 전부 다 +1이 되기 때문에 전체를 한번 더 더해준것과 같다.

여기에 이번에 새롭게 추가된 요리를 더해준것이 누적합이 된다.

 

예를 들어 3번째 요리를 추가했을 때 dp[3] 구하는 것을 식으로 설명하면 다음과 같다.

dp[3] = (1번째요리 * 3) + (2번째 요리 * 2) + (3번째 추가한 요리 * 1)  -> *1은 생략가능이다. 따라서 생략한다.

 

여기서, 2번째 요리를 추가했을 때의 dp[2]는

dp[2] = (1번째요리 * 2) + 2번째 추가한 요리

가 된다.

 

따라서 3번째 요리를 추가했을 때 dp[3] 을 다시 정의할 수 있다.

dp[3] = dp[2] + 누적합 + 이번에 추가한 요리

 

위 식을 활용하여 dp[i]를 이전 것 과 비교해서 큰 것으로 최신화 해간다.그리고 나서 0과 비교하여 (모든 음식을 버렸을 때와 비교) 큰 것을 택한다.

 

---

결   과  :

class Solution {
    public int maxSatisfaction(int[] satisfaction) {
        int res = 0;
        int n = satisfaction.length;
        int sum=0;

        // Collection 형으로 다시 배열 정의
        Integer sat[] = Arrays.stream(satisfaction).boxed().toArray(Integer[]::new);

        Arrays.sort(sat, Collections.reverseOrder());

        int dp[] = new int[n];
        dp[0] = sat[0];
        sum = sat[0];

        for(int i=1; i<n; i++) {
            dp[i] = Math.max(dp[i-1], dp[i-1] + sum + sat[i]);
            sum += sat[i];
        }
        res = Math.max(res, dp[n-1]);

        return res;
    }
}