Daily LeetCode Challenge - 1402. Reducing Dishes

Problem From.
https://leetcode.com/problems/reducing-dishes/

오늘 문제는 각 요리의 만족도가 적어진 staisfaction 배열이 주어졌을때, 요리를 몇개 만들지 않고 최대의 만족감값을 반환하도록 하는 문제였다.

이 문제는 DP 를 통해서 풀 수 있었는데,
먼저 satisfaction 배열을 오름차순으로 정렬한뒤, satisfaction 배열을 거꾸로 보면서 값을 하나씩 누적시켜나간다.
만족감이 가장 커지는 법은 제일 큰 수를 제일 뒤에 배치하여 가장 많이 더해야하므로, 제일 먼저 배열에서 가장 큰 값을 가져와서 누적시키면서, 누적시킨 값과, 현재 최대값을 비교하여, 더 큰쪽을 계속 가지고 가도록 하여 정답을 구할 수 있었다.

class Solution {
    fun maxSatisfaction(satisfaction: IntArray): Int {
        satisfaction.sort()
        var max = 0
        var curr = 0
        var diff = 0
        for (i in satisfaction.lastIndex downTo 0) {
            diff += satisfaction[i]
            curr += diff
            max = maxOf(max, curr)
        }
        
        return max
    }
}