[Leetcode] 2861. Maximum Number of Alloys

https://leetcode.com/problems/maximum-number-of-alloys/description/

기계가 여럿있고 기계마다 합금 제작을 위해 필요한 재료가 다르고, 재료별 재고와 비용 그리고 예산이 주어진 상태에서 합금을 가장 많이 만들라고 한다.

처음에는 2중 for문으로 돌리면서 기계별로 예산 써서 최대로 뽑아낼 수 있는 합금의 양을 다 계산한 후에 최대값을 고르는 방식을 사용하려고 했다.

class Solution:
    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:
        # index 1부터 시작함
        # binary search
        
        answer = 0
        for c in composition:
            answer = max(answer, createAlloy(c, stock.copy(), budget, cost))
        return answer

def createAlloy(machine, stock, budget, cost):
    count = 0

    while True:
        chk = True
        for i in range(len(stock)):
            while stock[i] < machine[i]:
                budget -= cost[i]
                stock[i] += 1
            
            if budget < 0:
                chk = False
                break

            stock[i] -= machine[i]
         
        if chk:
            count += 1
        else:
            break
    return count

그리고 시간초과가 났다.

만들려고 하는 합금의 수를 변수로 두고 바이너리 서치로 전환했다. 기계별로 binary search를 통해서 최대로 만들 수 있는 합금을 계산했다. 최대치를 계산할 때는 mid로 먼저 기계에 할당하고 예산이 부족한지, 남는지에 따라서 mid를 조정했고 최대값을 만들었다. 계산할 때마다 전체의 최대값을 갱신했고 그게 정답이 되었다.

class Solution:
    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:
        # 만들 수 있는 합금의 최대값
        # 기계를 선택하면 결과는 알아서 나옴

        # 개수를 기준으로 budget을 넘지않은 채로 합금 만들 수 있는 기계를 찾아야하나?
        # binary search 100번
        answer = 0


        for c in composition:
            tmp = 0
            start = 0
            end = 1000000000

            while start <= end:
                mid = (start + end) // 2

                over = createAlloy(c, stock, cost, mid)
                print(c, mid, over)

                if over > budget:
                    end = mid - 1
                else:
                    tmp = mid
                    start = mid + 1
            print(c, tmp)
            answer = max(answer, tmp)
        return answer
            

            

def createAlloy(machine, stock, cost, order):
    totalcost = 0
    
    for i in range(len(machine)):
        # 추가 구매 비용은 이만큼
        if stock[i] < machine[i] * order:
            totalcost += cost[i] * (machine[i] * order - stock[i])

    return totalcost

최초에 이 코드로 돌렸을 때 시간초과는 안 났으나 두 번 실패했다. binary search할 때 사용하는 end값이 너무 작아서 발생한 문제였다. end값을 재고의 최대 + 예산의 최대로 계산해서 하면 될 것 같았는데 문제 풀 당시에는 생각이 안나서 그냥 0을 계속 붙여줬다.