[백준] 예산 풀이

하한액(start)을 1, 상한액(end)을 arr의 최댓값으로 두었습니다.
이진 탐색을 위해 sort 될 예정이니 arr[-1]이 최대가 됩니다.

이진 탐색을 통하여 mid를 (start + end) / 2로 두고, 이진 탐색을 시작합니다.
total이라는 변수에 arr의 각 요소와의 연산을 통한 값을 담습니다.

그리고 total의 값이 M보다 작거나 같은 경우,
우리가 찾고자 하는 값이 mid를 포함한 오른쪽 지역이라는 것을 알 수 있으므로
0으로 초기화 되어있던 total_cnt 변수에 mid와 total_cnt의 최댓값을 넣어 주고, start를 mid + 1로 바꿔줍니다.

그렇지 않은 경우(즉, 이미 값을 넘어간 경우)
end를 mid - 1로 바꿔줍니다.

즉, 예산들 중 최댓값이 정답이니 예산 후보들을 total_cnt에 저장한 뒤, max로 업데이트 한다고 생각하시면 됩니다.

pypy3 기준으로 메모리 123220KB, 시간은 108ms 소요되었습니다.

def binary_search():
    global total_cnt
    start = 1
    end = arr[-1]  # arr의 최댓값

    while start <= end:

        mid = (start + end) // 2
        total = 0

        for i in arr:

            if i <= mid:
                total += i

            else:
                total += mid

        if total <= M:  # 예산보다 작거나 같은 경우, mid를 늘려야 한다.
            start = mid + 1
            total_cnt = max(total_cnt, mid)

        else:  # 예산보다 큰 경우, mid를 줄인다.
            end = mid - 1


N = int(input())
total_cnt = 0  # 최소 금액

arr = list(map(int, input().split()))

M = int(input())
arr.sort()
binary_search()
print(total_cnt)