[백준] 2512번 - 예산

아이디어

요청 배정여부에 따른 조건문을 제외하고는 지난주에 풀었던 이진탐색 코드와 매우 유사했다.
모든 요청이 배정될 수 없는 경우에 mid값을 상한액으로 생각하여 최대 상한액을 찾는 방식으로 구현했다.

코드

# 예산
import sys
N = int(sys.stdin.readline().rstrip())
money = list(map(int,sys.stdin.readline().split()))
M = int(sys.stdin.readline().rstrip())

if sum(money) < M: # 모든 요청이 배정될 수 있는 경우
    print(max(money))
else: # 모든 요청이 배정될 수 없는 경우 -> 이진 탐색
    start = 1
    end = max(money)
    result = 0
    while (start <= end):
        check = 0
        mid = (start + end) // 2 # 상한액 지정
        for m in money:
            if m <= mid: # 상한액 이하의 예산요청
                check += m
            else: # 상한액 배정
                check += mid
        if check > M: # 예산액 초과
            end = mid - 1
        else:
            result = mid
            start = mid + 1
    print(result)