[LeetCode] 2530. Maximal Score After Applying K Operations

https://leetcode.com/problems/maximal-score-after-applying-k-operations/description/?envType=daily-question&envId=2024-10-14

leetcode - Maximal Score After Applying K Operations

문제 유형: 우선순위 큐, 그리디

문제 난이도: Medium

 

문제

You are given a 0-indexed integer array nums and an integer k. You have a starting score of 0.

In one operation:

1. choose an index i such that 0 <= i < nums.length,
2. increase your score by nums[i], and
3. replace nums[i] with ceil(nums[i] / 3).

Return the maximum possible score you can attain after applying exactly k operations.

The ceiling function ceil(val) is the least integer greater than or equal to val.

 

당신은 정수 배열 nums와 정수 k를 받습니다. 당신은 0점부터 시작합니다.

1. nums.length이내의 유효한 인덱스 i를 고른다.

2. nums[i]만큼 점수를 올린다.

3. nums[i]를 ceil(nums[i]/3)으로 저장한다.

 

정확히 k번의 연산으로 얻을 수 있는 최대 점수를 구하시오.

 

풀이

매번의 연산마다 가장 큰 값을 더해야 한다.

최대 힙 우선순위 큐로 가장 큰 값을 관리할 것이다.

우선, 배열의 모든 요소들을 우선순위 큐에 넣는다.

 

그 뒤, 연산을 k번 적용해준다:

  우선순위 큐의 톱에서 pop해온다.

  그 값을 정답 변수에 누적한다.

  톱의 값을 3으로 나누고, 올림처리하여 다시 톱에 넣는다.

 

최종적인 답안을 리턴한다.

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    long long maxKelements(vector<int>& nums, int k) {
        priority_queue<int> maxHeap;
        long long ans = 0;

        for(int num : nums) {
            maxHeap.push(num);
        }

        for(int i = 0; i < k; ++i) {
            int x = maxHeap.top();
            maxHeap.pop();
            ans += x;
            x = ceil((double)x/3);
            maxHeap.push(x);
        }

        return ans;
    }
};