[LeetCode] 1760. Minimum Limit of Balls in a Bag

https://leetcode.com/problems/minimum-limit-of-balls-in-a-bag/description/

leetcode - Minimum Limit of Balls in a Bag

문제 유형: 이진 탐색

문제 난이도: Medium

 

문제

You are given an integer array nums where the ith bag contains nums[i] balls. You are also given an integer maxOperations.

You can perform the following operation at most maxOperations times:

• Take any bag of balls and divide it into two new bags with a positive number of balls.
  • For example, a bag of 5 balls can become two new bags of 1 and 4 balls, or two new bags of 2 and 3 balls.

Your penalty is the maximum number of balls in a bag. You want to minimize your penalty after the operations.

Return the minimum possible penalty after performing the operations.

 

nums[i]개의 공을 가진 가장들의 정보가 nums배열로 주어진다.

정수 maxOperations도 받는다.

당신은 최대 maxOperations번 다음의 연산을 할 수 있다:

-> 가방을 골라서 두 가방에 공을 나눠담기.

 

가방에 있는 공의 개수의 최대값이 패널티이다.

패털티의 가능한 최소값을 구하시오.

 

풀이

최대값을 최소화(minimize the maximum)라는 키워드는 이진 탐색의 힌트가 된다.

패널티의 범위는 1부터 가장 큰 수까지가 된다.

 

left를 1, right는 배열에서 가장 큰 수로 한다.

중앙값 m을 구해본다.

모든 가방에 대해 최대 m개의 공을 가지도록 만들려면 필요한 연산의 수를 구한다.

예를 들어, nums[i] = 7, m= 3이라면, (7-1/3) = 2이다. 즉, 2번 필요하다.

최대 m개씩 가지게 되면, 가방의 개수는 ceil(nums[i]/m)개여야 한다.

그러나 기존의 가방이 있으므로,  1개를 빼줘야 한다.

그래서 (nums[i]-1)/m으로, 먼저 피제수에 1을 뺴고 m을 나눈 몫이 실제 연산 수, 즉 추가되는 가방 수가 되는 것이다.

 

m이 maxOperations이하라면, m의 크기를 더 줄여볼 수 있다. r = m으로 하고 다시 이진탐색을 계속한다.

그게 아니라면, m의 크기를 키워야 한다. l = m+1로 하고 다시 이진탐색을 계속한다.

이를 l이 r보다 작은동안 계속한다.

 

최종적으로 r에는 minimized maximum이 남아있다.

 

 

코드

C++

class Solution {
public:
    int minimumSize(vector<int>& nums, int maxOperations) {
        int n = nums.size();
        int l = 1, r = *max_element(nums.begin(), nums.end());

        while(l < r) {
            int m = (l+r)/2;
            long long cnt = 0;
            for(int j = 0; j < n && cnt <= maxOperations; ++j) cnt += (nums[j]-1)/m;
            if(cnt <= maxOperations) r = m;
            else l = m+1;
        }

        return r;
    }
};