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