2064. Minimized Maximum of Products Distributed to Any Store

Problem : https://leetcode.com/problems/minimized-maximum-of-products-distributed-to-any-store/

Difficulty : Medium

Status : Solved

Time : ??:??:??

---

---

풀이

헤매고 헤매다가 힌트 하나를 보고 깨달은 문제. binary search의 응용 문제이다.

임의의 수 m에 대해서 모든 product를 m 이하가 되도록 나눌때, 이 product의 총 개수가 n이하인지를 검사하면 된다. 이를 기준으로 binary search를 수행해 최소가 되는 m(즉 lower bound)를 찾는 게 목표가 되겠다

class Solution:
    def check(self, n, quantities, target):
        res = 0
        for q in quantities :
            res += q // target
            if q % target :
                res += 1
            if res > n :
                return False
        return True
    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:
        start, end = 1, max(quantities)
        
        while start < end :
            mid = (start + end) // 2
            if self.check(n, quantities, mid) :
                end = mid
            else : 
                start = mid + 1
        return end