[LeetCode] 2861. Maximum Number of Alloys(C++)

문제

 

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

LeetCode - The World's Leading Online Programming Learning Platform

 

 

풀이

 

난이도: Medium 

 

주간 Leetcode contest문제를 풀어보자~~

https://leetcode.com/discuss/general-discussion/4053842/weekly-contest-363

Loading...

 

 

 

처음 봤을 땐 이진 검색을 써야 하는 지도 전혀 몰랐다.

마땅히 방법이 없어서 브루트 포스로 풀었더니 얄짤없이 시간초과였다.

 

각 기계당 목표 alloy 개수를 1에서 하나씩 늘려가면서 for문을 돌면, stock의 최대 개수가 1e8이기 때문에 시간초과가 발생하기 쉽다.

 

 

 

 

 

따라서 해당 문제는 목표 alloy개수를 mid로 설정하는 이진 탐색을 구현해야 한다.

 

 

일단 이진 탐색의 최대 범위를 설정해야한다.

composition은 최소 1, stock은 최대 1e8   -> 추가 구매 없이도 1e8개 생성가능

cost는 최소 1, budget은 최대 1e8이므로  -> 구매로 생성 가능한 개수도 1e8

즉, 1e8 * 2이다.

 

이제 low와 high의 중간을 mid(목표 alloy개수)로 설정하고,

mid가 예산으로 만들 수 있는지 모든 기계에서 확인한다.

 

시간 복잡도를 계산해 보면 O( log(1e8 * 2)*n) 정도로 충분히 탐색 가능한 수준이 되었다.

 

 

 

 

코드

 

 

 

 

 

 

여담으로 시간 소요가 너무 형편이 없어서 상위 0.1%의 코드를 찾아보았는데

 

 

이런 식으로 자신만의 최적화 세팅을 미리 걸어두고 코딩하는 것 같다... (무섭다...)