[LeetCode] 2064. Minimized Maximum of Products Distributed to Any Store

https://leetcode.com/problems/minimized-maximum-of-products-distributed-to-any-store/description/?envType=daily-question&envId=2024-11-14

leetcode - Minimized Maximum of Products Distrivbuted to Any Store

문제 유형: 이진 탐색

문제 난이도: Medium

 

문제

You are given an integer n indicating there are n specialty retail stores. There are m product types of varying amounts, which are given as a 0-indexed integer array quantities, where quantities[i] represents the number of products of the ith product type.

You need to distribute all products to the retail stores following these rules:

• A store can only be given at most one product type but can be given any amount of it.
• After distribution, each store will have been given some number of products (possibly 0). Let x represent the maximum number of products given to any store. You want x to be as small as possible, i.e., you want to minimize the maximum number of products that are given to any store.

Return the minimum possible x.

 

n개의 창고와 quantites[i]는 i번째 물건의 개수를 의미하는 배열 quantities가 주어집니다.

n개의 창고에 정확히 분산시켜야 합니다.

단, 창고에는 한 가지의 물건만 적재가능합니다.

창고에 하나 이상의 물건이 있어야 합니다.

 

분산된 한 창고당 물건의 개수의최대값들 중 최소를 구하시오.

 

풀이

창고당 물건의 최대값을 최소로 만들려면, 최대한 고르게 분포시켜야 한다.

요소들의 값들 중 가장 큰 값은 1부터 10^5일 수가 있다.

최선의 방법은, 이진 탐색으로 최적의 값을 구하는 것 뿐이다.

 

left를 1, right를 10^5로 두고, 중간값을 구해서 가능한지 계속 질의하는 것이다.

한 창고에 물건을 최소 x개 둔다 했을 때, i번째 물건을 넣을 수 있는 최대 창고 수는 (quantities[i] + x-1)/x이다.

즉, ceil(quantities[i]/x)이다.

이 누적이 n보다 크면, 분산이 불가능하다.

 

분산이 가능하다면, 더 높은 범위로 잡아서, 더 고르게 분포시키도록 만든다.

 

최종적으로 left는 이전 가능한 mid의 +1이 되는데, 이는 최대한 고르게 분포되어있는 상태에서 1개의 물건을 더 넣는다는 의미이다.

 

코드

C++

class Solution {
public:
    bool canDistribute(int x, vector<int>& quantities, int n) {
        int sum = 0;
        for(int q : quantities) {
            sum += (q+x-1)/x;
        }
        return sum>n;
    }
    int minimizedMaximum(int n, vector<int>& quantities) {
        int left = 1, right = 100000, mid;
        while(left < right) {
            mid = (left + right)/2;
            if(canDistribute(mid, quantities, n)) left = mid+1;
            else right = mid;
        }

        return left;
    }
};