https://programmers.co.kr/learn/courses/30/lessons/43237
- flow
한동안 다른 일로 바빠서 예전에 풀어놨던 문제인데 정리를 못했었다.
기억이 완전하진 않지만 이것도 이분탐색 알고리즘을 이용하면 되는 문제이다.
예산 배정 상한액을 구하는데 min=0, max=max(budgets) 부터 스타트하면 깔끔한 것 같다.
처음에 풀었을 때, 효율성 테스트 1,2번 이었나? 정답이 안 나와서 효율성 문제인 줄 알고 여러 뻘짓을 했었던 기억은 확실히 난다..
def solution(budgets, M):
Min = 0
if sum(budgets) < M:
return max(budgets)
Max = max(budgets)
budgets.sort()
while Max > Min:
if Max == Min + 1:
return Min
mid = (Max + Min) // 2
ma = len(budgets)-1
mi = 0
while ma > mi:
midd = (ma + mi) // 2
if budgets[midd] > mid:
ma = midd
else:
mi = midd
if ma == mi + 1:
break
Sum = mid * (len(budgets)-ma)
for e in budgets[:ma]:
if Sum > M:
break
Sum += e
if Sum > M:
Max = mid
else:
Min = mid
return Min이런 식으로 mid 값 테스트하는 것도 이분탐색을 한번 더 이용해서 효율성을 많이 끌어 올렸었다.. 근데 나중에야 효율성문제가 아니라 답이 틀렸다는 것을 깨닫고.. 조건 하나 바꿔서 올 correct를 띄운 기억이.. - result
https://github.com/songjy6565/alg-py/blob/master/programmers/level3/A13.py
