Leetcode 2305. Fair Distribution of Cookies

https://leetcode.com/problems/fair-distribution-of-cookies/description/

Fair Distribution of Cookies - LeetCode

 

문제

정수로 이루어진 배열 cookies가 주어진다. 이 배열의 각 요소는 각 주머니에 담긴 cookie의 개수를 나타낸다. 또한 정수 k가 함께 주어지는데 쿠키를 나누어 받을 사람의 수를 의미한다. 각 주머니에 담긴 쿠키들을 낱개로 아이들에게 줄 수 없으며 묶음단위로 아이들에게 줄 수 있다.

 

이때 가장 불공정한 분배란 모든 쿠키들을 한명의 아이에게 주는 것을 의미한다.

 

이러한 정보를 바탕으로 불공정한 배분이 최소가 될 수 있는 분배를 찾아 그 분배의 최대값을 반환하라

 

코드

class Solution:

    def distributeCookies(self, cookies: list[int], k: int) -> int:

        self.answer = []

        m = max(cookies)

        self.substition = m * k

        if len(cookies) == k:

            return m

        def r(distribute, n):

            if n >= len(cookies):

                m = max(distribute)

                substition = sum(map(lambda x: m - x, distribute))

                if self.substition > substition:

                    self.substition = substition

                    self.answer = distribute[:]

                return

            for i in range(k):

                distribute[i] += cookies[n]

                r(distribute, n + 1)

                distribute[i] -= cookies[n]

        r([0] * k, 0)

        # print(self.answer)

        return max(self.answer)

---

쿠키의 개수와 아이들의 수가 같으면 단순 max값을 리턴해주어 시간단축할 수 있었음.