[백준] 2512번 예산

💡문제접근

• 탐색 범위를 효율적으로 좁혀 나가는 이분 탐색에 대한 문제다.
• 중간값을 정한 후 해당 중간값이 지방의 예산요청값보다 작으면 그대로 더해주고 만약 지방의 예산요청값보다 크다면 지방의 예산요청값을 더해준다.
• for문을 돌려 N개 지방의 예상 총 예산이 총 예산 M보다 작은 시점이 나오게 된다면 그 때의 중간값을 출력한다.

💡코드(메모리 : 31720KB, 시간 : 68ms)

def binary_search(data):
    start = 0
    end = max(data)
    li = []
    while True:
        mid = (start + end) // 2
        if start > end:
            break
        total_budget = 0
        for i in budget:
            total_budget += min(i, mid)
        if total_budget > M:
            end = mid - 1
        else:
            start = mid + 1
        li.append([mid, total_budget])
    return li

N = int(input())
budget = list(map(int, input().split()))
M = int(input())

result = sorted(binary_search(budget), key = lambda x : (-x[1], x[0]))
for i in range(len(result)):
    if result[i][1] <= M:
        print(result[i][0])
        break

💡소요시간 : 11m