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