[LeetCode] 2226. Maximum Candies Allocated to K Children (Python)

 

 

난이도: Medium

Problem Description

---

 

You are given a 0-indexed integer array candies. Each element in the array denotes a pile of candies of size candies[i]. You can divide each pile into any number of sub piles, but you cannot merge two piles together.

 

You are also given an integer k. You should allocate piles of candies to k children such that each child gets the same number of candies. Each child can be allocated candies from only one pile of candies and some piles of candies may go unused.

 

Return the maximum number of candies each child can get.

 

Problem Example

---

Example 1:

Input: candies = [5,8,6], k = 3
Output: 5
Explanation: We can divide candies[1] into 2 piles of size 5 and 3, and candies[2] into 2 piles of size 5 and 1. 
We now have five piles of candies of sizes 5, 5, 3, 5, and 1. 
We can allocate the 3 piles of size 5 to 3 children. 
It can be proven that each child cannot receive more than 5 candies.

Example 2:

Input: candies = [2,5], k = 11
Output: 0
Explanation: There are 11 children but only 7 candies in total, so it is impossible to ensure each child receives at least one candy. 
Thus, each child gets no candy and the answer is 0.

 

Constraints

---

• 1 <= candies.length <= 105
• 1 <= candies[i] <= 107
• 1 <= k <= 1012

 

✏️ Solution

---

def can_get(candies, k, mid):
    cnt = 0

    for candy in candies:
        cnt += candy//mid

    return cnt >= k

class Solution:
    def maximumCandies(self, candies: List[int], k: int) -> int:
        sum_candies = sum(candies)
        if sum_candies < k:
            return 0

        left, right = 1, sum_candies//k + 1

        while left <= right:
            mid = (left + right) // 2

            if can_get(candies, k, mid):
                left = mid + 1
            else:
                right = mid - 1

        return right

 

k명 아이들에게 사탕을 줄 수 있는 갯수는 1개 ~ 총 캔디의 합 // k개 까지 있다.

 

이 중 k명의 아이들에게 똑같은 갯수로 줄 수 있는 최대의 사탕의 수를 구하면 된다.

 

이는 이진 탐색으로 쉽게 구할 수 있다.

 

일단 candies의 합이 k보다 작으면 모든 아이들에게 같은 양의 사탕을 줄 수 없기 때문에 0을 반환한다.

 

left, right를 1과 sum(candies)//k + 1로 지정해주고 left가 right보다 작거나 같을 동안 반복했다.

 

(left+right)//2를 통해 mid를 구해주고 각 candy를 mid로 나눈 값들을 모두 더하면 몇명의 아이들에게 mid만큼 사탕을 줄 수 있는지 구할 수 있다. 

 

예를 들어, candies가 [4, 7, 5]이고 k가 4, 현재 mid가 3이라고 한다면, cnt는 다음과 같이 수행된다.

cnt = 4//3 = 1

cnt = cnt + 7//3 = 1 + 2 = 3

cnt = cnt + 5//3 = 1 + 2 + 1 = 4

 

이때 cnt는 k값과 같기 때문에 true를 반환한다.

 

만약 이러한 연산뒤에 cnt가 k보다 작다면 false를 반환한다.

 

즉, 현재 mid만큼 아이들에게 같은 양의 사탕을 줄 수 있다면 더 많이 줄 수 있는지 확인한다.

 

이를 위해 left를 mid + 1 해준다.

 

만약 k명의 아이들에게 mid 만큼 사탕을 줄 수 없으면 right를 mid - 1하여 줄 수 있는 사탕의 갯수를 줄여 다시 확인한다.

 

위 과정을 반복하다 left가 right보다 크거나 같아지면 반복문은 종료된다.

 

마지막에는 right를 반환하여 정답을 맞출 수 있었다

 

⚙️ Runtime & Memory

---

 

---

문제: 2226. Maximum Candies Allocated to K Children 

 

깃허브: github

algorithmPractice/LeetCode/1335-maximum-candies-allocated-to-k-children at main · laewonJeong/algorithmPractice