[Leetcode 2064번 문제] 2064. Minimized Maximum of Products Distributed to Any Store

 

문제 상황

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.

제품배열이 존재하고 i번은 i번째 프로덕트의 개수를 의미한다. 이 배열 요소들을 다음의 룰로 n개의 상점에 나눔

n개 각각의 항목에는 최대 한종류만 들어갈 수 있음, (안 들어갈 수도 있다는 듯) 그리고 이렇게 나눈 곳에서 얻을 수 있는 가장 큰 값이 존재할건데 가능한 값 중 최소를 구해야한다.

입력

• m == quantities.length
• 1 <= m <= n <= 105
• 1 <= quantities[i] <= 105

출력

가능한 정수 값

과정

nlog(m)으로 푸는 방법으로 접근하려한다. 우선 가능한 범위는 최소 1, 최대 max(quantities)라고 할 수 있다. 여기서 어떤 값이 정확히 내가 원하는 값인가. 그걸 위해서 quantities수들을 나눠보는건 모든 수마다 다른 기준을 적용해야해서 시간도 오래걸리고 복잡하다.

각각의 요소마다 각각의 기준을 적용해야하기 때문. 그렇기 때문에 관점을 바꿔서 최대 수 자체를 미리 고정한다

그럼 quantities의 각각의 타입들은 이렇게 정해진 개수로 나눠질 것이다.

각각의 타입의 정해진 상점 개수 quantity / 정해진 최대값 + (quantity % 정해진 최대값 ≠ 0 에 대한 불 값) 개.

이문제는 물품을 못받은 상점이 몇개있는지는 전혀 궁금해하지 않는다. 무조건 각각의 type은 최대값이 정해진 상태에서 최소의 종류로 나뉘면 된다.

그래서 나는 저 각각의 quantities의 상점 개수가 총 n개를 넘는지 안넘는지만 보면된다 만약 넘는다면 정해진 최대값이 너무 작다는 뜻이고, 작거나 같다면 가능한 정답중에 하나지만 이게 최소인지는 알 수 없다.

그래서 이문제는 upperbound를 사용하는 이진탐색으로 해석할 수 있게된다.

알고리즘

class Solution {
public:
    int minimizedMaximum(int n, vector<int>& quantities) {
        long long total = 0;
        int maxN = 0;
        for (int type : quantities)
        {
            total += type;
            maxN = max(maxN, type);
        }
        if (total <= n)
        {
            return 1;
        }

        int minN = 1;
        while (minN < maxN)
        {
            int mid = (minN + maxN) / 2;
            int tmp = 0;
            for (int quantity : quantities)
            {
                tmp += (quantity) / mid + ((quantity) % mid != 0);
            }
            if (tmp > n)
            {
                minN = mid + 1;
            }
            else
            {
                maxN = mid;
            }
        }
        return maxN;
    }
};