[백준 Python] 2512번 예산

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

2512번: 예산

 

문제정리

N개의 예산 신청을 예산액에 맞게 부여해야 한다.

기준 예산액을 정한 후 기준 예산액보다 작은 경우 그대로 배정, 클 경우 기준 예산액으로 부여한다.

 

문제풀이

기준 예산액을 정해야한다.

기준 예산액을 정한 후 예산액을 계산해서 통과인지 아닌지 찾기

기준 예산액을 1부터 최대 예산액 까지 증가시키며 조건을 만족하는지 찾을 수 있다. ( 브루트 포스 )

이분 탐색으로 기준 예산액을 구해보자

만약 통과라면 기준 예산액을 높이고 불통이라면 기준 예산액을 낮춘다.

N 개의 가장 큰 예산 신청이 기준 예산액에 영향을 줌

따라서 lo = 0 , hi = max_예산신청 으로 두며 이분탐색을 하자

 

# 예산 배정하기
# 모든 요청 가능하면 그대로 배정
# 안된다면 특정한 상한액으로 배정 (상한액 이하는 그대로 배정)

N = int(input())
arr = []

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

M = int(input()) # 총 예산


lo = 0
hi = arr[-1]
ans = 0

def judge(mid): # mid 값으로 예산 배정이 가능한가?
    total = 0
    for i in range(N):
        if arr[i] > mid:
            total += mid
        else :
            total += arr[i]
    return total <= M


while lo <= hi:
    mid = (lo+hi) // 2
    if(judge(mid)):
        lo = mid + 1
        ans = mid
    else :
        hi = mid - 1

print(ans)