문제는 budget, stock, cost, composition이 주어졌을 때, 이를 조합하여 최대로 만들 수 있는 alloys의 갯수를 return하는 문제이다. 나는 문제가 주어지자마자 바로 일반 구현으로 풀었으나, 첫 째로 1) 여러가지 케이스에서 오류가 났었고, 이를 올바르게 수정하였으나 둘 째로 2) Time Limit Exceeded에 걸렸다. 조금 더 문제를 살펴보니 Binary Search로 풀어야 한다는 것을 알았다. ( 내 풀이 방식은 매 iteration 마다 남은 stock을 체크하고 이에 대한 결과 값을 만드는 형식으로 풀이하였다. )
정답 풀이는 다음과 같다.
max_alloys를 찾기 위한 binary search를 구현한다. 이 때 탐색범위는 0 ~ 10**9 (넉넉히 잡음)
해당 mid 값을 택할 시, 얻어지는 값을 계산한다.
money = 0
for j in range(n):
req = composition[i][j] * mid
req -= stock[j]
if req >= 0:
money += req * cost[j]
만약 이 값이 budget 이하라면, ans로 max(ans, mid) 값을 채택하고, low 값을 mid + 1로 갱신한다.
만약 이 값이 budget 이상이라면, high 값만 mid - 1로 갱신한다.
low ≤ high를 만족하는동안 계속 반복한다.
⇒ 즉, 나의 방식은 for문을 통해 max 값을 하나씩 늘려가며 찾았다면, 정답 풀이는 max 값을 0 ~ inf 값 내에서 binary search 형식으로 찾아 효율성을 높였다.
요즘 계속 Binary Search 문제에서 걸리는 것 같다. 이 카테고리에 대해 집중적으로 공부하고 넘어갈 필요가 있을 듯 하다. 월요일 날 날잡고 한번 쭉 풀어보자.