3075. Maximize Happiness of Selected Children

Problem : https://leetcode.com/problems/maximize-happiness-of-selected-children

 

Difficulty : Medium

 

Status : Solved

 

Time : ??:??:??

 

---

 

문제 설명

 

---

 

풀이

 

릿코드에서 맞닥뜨린 한국적인(?) 문제. 지금껏 릿코드 문제를 풀어서 느꼈던 점은. 왠지 백준 골드문제를 달아줘도 손색없을 난이도였다.

 

그리디로 접근해보자. 어떻게 사람을 뽑던 간에, 최종적으로 k명의 사람을 뽑으므로 감소치는 최대 k*(k-1)/2명이 될 것이다. happiness value는 음수가 될 수 없다. 즉 매 순간 행복도가 최대치인 아이들을 뽑고, 어느 시점에서 행복도 최대치가 0이라면 감소는 더 이상 적용되지 않는다. 즉

 

• 내림차순으로 정렬
• k까지의 합을 구하되, 각 원소는 max(0, value - time)의 형태로 더해짐

으로 풀이해볼 수 있다.

 

풀이 코드(Python)

class Solution:
    def maximumHappinessSum(self, happiness: List[int], k: int) -> int:
        happiness.sort(key = lambda x : -x)
        answer = 0
        for i in range(k) :
            answer += max(0, happiness[i] - i)
        return answer

 

 

풀이 코드(Go)

func maximumHappinessSum(happiness []int, k int) int64 {
    var answer int64
    sort.Slice(happiness, func(i, j int) bool {
        return happiness[i] > happiness[j]
    })
    for i := 0; i < k; i++ {
        answer += int64(math.Max(0., float64(happiness[i] - i)))
    }
    return answer
}