[LeetCode] 3075. Maximize Happiness of Selected Children

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

leetcode - Maximize Happiness of Selected Children

문제 유형 : 정렬 / 그리디

문제 난이도 : Medium

 

문제

You are given an array happiness of length n, and a positive integer k.

There are n children standing in a queue, where the ith child has happiness value happiness[i]. You want to select k children from these n children in k turns.

In each turn, when you select a child, the happiness value of all the children that have not been selected till now decreases by 1. Note that the happiness value cannot become negative and gets decremented only if it is positive.

Return the maximum sum of the happiness values of the selected children you can achieve by selecting k children.

 

n개짜리 정수배열 happiness와 양의정수 k가 들어있습니다.

n명의 아이들이 서있습니다.

happiness[i]에는 i번째 애들의 행복도가 나타나 있습니다.

당신은 k명의 아이들을 k턴내로 골라야합니다.

 

각 턴마다, 당신이 아이를 고르면, 선택받지 못한 아이들은 1씩 행복도가 감소합니다.

행복도는 음수가 될 수 없습니다. 즉, 양수일때만 1씩 감소합니다.

선택받은 아이들의 최대 행복도의 합을 구하시오.

 

풀이

happiness 배열을 내림차순정렬을 하고, 

for문으로 배열을 순차적으로 순회하면서 

happiness[i] - i만큼 누적시키면 됩니다.

i = 0, 즉 0턴 일때, 제일 큰 아이를

i = 1, 즉 1턴일때, 두 번째로 행복도가 큰 아이를 선택한다는 뜻입니다.

...

i = k일때, 즉 마지막 턴에는 k-1번째로 행복도가 큰 아이를 선택한다는 뜻입니다.

 

코드

C++

class Solution {
public:
    long long maximumHappinessSum(vector<int>& happiness, int k) {
        sort(happiness.begin(), happiness.end(), greater<int>());
        long long ans = 0;
        for(int i = 0; i < k; i++) {
            ans += max(happiness[i] - i, 0);
        }

        return ans;
    }
};