[백준] S2. boj2512 예산 / 분류 : 이분 탐색

https://www.acmicpc.net/problem/2512

2512번: 예산

import sys
input = sys.stdin.readline

N = int(input()) #지방의 개수
li = list(map(int, input().split())) # 각 지방의 예산 요청 배열
M = int(input()) #총 예산

#예산 요청의 합이 총 예산보다 작으면 가장 큰 값 출력
if sum(li) <= M:
    print(max(li))
#예산 요청의 합이 총 예산보다 클 경우
else:
    result = 0
    start = 0
    end = max(li)
    while start <= end:
        mid = (start + end) // 2
        sums = 0
        #예산 요청의 합 구하기
        for l in li:
            #예산 요청이 mid 이하이면 예산 요청 금액 그대로 더하기
            if l <= mid:
                sums += l
            #예산 요청이 mid 초과이면 mid 금액 더하기
            else:
                sums += mid
        #예산 총합이 총 예산보다 작으면 start를 mid + 1로
        if sums <= M:
            start = mid + 1
        #예산 총합이 총 예산보다 크면 end를 mid - 1로
        else:
            end = mid - 1
    print(end)