100일 DSA 코딩 챌린지 중 Day 85

Source: Dev.to

Challenge Overview

새로운 도전에 도전합니다: GeeksforGeeks POTD를 매일 풀고 해결 과정을 공유합니다! 💻🔥

Problem

Minimum time to fulfil all orders
GeeksforGeeks – Minimum time to fulfil all orders

Difficulty: Hard Accuracy: 66.7%

Geek은 파티를 열기 위해 손님에게 정확히 n개의 도넛이 필요합니다. Geek은 근처 레스토랑에 도넛을 주문하기로 했으며, 그 레스토랑에는 m명의 셰프가 있고 각 셰프는 등급 r을 가지고 있습니다.

Solution Approach

문제는 답(시간)에 대해 이진 탐색을 이용해 해결할 수 있습니다. 주어진 시간 mid에 대해 각 셰프가 만들 수 있는 도넛 수를 계산하고 합산합니다. 총합이 n 이상이면 더 작은 시간을 시도하고, 그렇지 않으면 시간을 늘립니다.

def minimum_time(ranks, n):
    # Helper to compute donuts a chef with rank r can make in given time t
    def donuts_made(r, t):
        # Solve r * k * (k + 1) / 2 = n:
                break
        if total >= n:
            high = mid
        else:
            low = mid + 1
    return low

함수 minimum_time은 셰프들이 최소 n개의 도넛을 생산하는 데 필요한 가장 짧은 시간을 반환합니다.