2512-예산

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

2512번: 예산

이분 탐색 중 파라매트릭 서치를 구현해보는 문제이다. 어렵게 생각하지 말고 기본적인 이분탐색 구현에 초점을 맞추면 쉽게 해결할 수 있다. 라이브러리를 불러와서 이분탐색 함수를 쓸 필요도 없다.

 

입력받은 예산들 중 가장 큰 값의 절반으로 중간점을 잡고 중간점과 각 예산 중 작은 값들을 더한 값이 예산 총액을 넘어가는지 확인하면서 이를 반복한다.

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

lo = 0
hi = max(req)
mid = hi//2
ans = 0

def is_possible(mid):		# 총 합이 예산 총액보다 작으면 True
    return sum(min(r,mid) for r in req) <= M

while lo <= hi:
    if is_possible(mid):	# 상한선을 mid로 했을 때 예산이 아직 남았으면	
        lo = mid + 1		# 이제 상한선의 가능범위가 mid+1 부터 hi까지로 범위가 좁아진다
        ans = mid
    else:
        hi = mid - 1
    mid = (lo + hi) // 2
print(ans)