합성을 번 하면 암모니아를 통 얻는다. 필요한 최소 합성 횟수는 이다. 그보다 많이 합성하려면 더 많은 원료가 필요하므로 최소 비용을 낮출 수 없다. 따라서 질소 통과 수소 통을 사는 문제를 각각 풀면 된다.
각 원료를 통당 가격이 낮은 거래처부터 재고 한도까지 구매한다. 더 싼 거래처에 재고가 남았는데 더 비싼 거래처에서 구매했다면, 그중 한 통을 더 싼 곳에서 사도록 바꿀 수 있다. 이 교환은 구매 총량을 유지하면서 비용을 줄인다. 가격이 같은 거래처의 구매 순서는 비용에 영향을 주지 않는다. 따라서 통당 가격을 오름차순으로 정렬하고, 각 거래처에서 남은 필요량과 재고량 중 작은 만큼 사면 최적이다. 어느 원료든 재고를 모두 사용하고도 필요량이 남으면 -1을 출력한다.
라 하면 시간 복잡도는 이고 공간 복잡도는 이다. 구매하는 양은 총 통이고 통당 가격은 최대 이므로, 가능한 최소 비용의 최댓값은 이다.
Solution written by GPT