[백준] 2512번 예산 파이썬 코드

코드

 

종료조건

1. sum_request가 budget을 넘지 않는 경우

2. request에 들어있는 값 사이에서 예산 타협점을 찾는 경우

3. request에 들어있지 않은 값에서 예산 타협점을 찾는 경우

 

처음에 3번을 생각 못해서 start를 min(request)로 했다가 틀렸다. 케이스를 잘 생각하자.

m = int(input())
request = list(map(int, input().split()))
budget = int(input())

sum_request = sum(request)
result = 0
start = 1
end = max(request)

while (start <= end):
  if sum_request <= budget: 
    result = max(request)
    break
  new_budget = []
  mid = (start + end) // 2
  for i in request:
    if i <= mid: new_budget.append(i)
    else: new_budget.append(mid)
  if sum(new_budget) <= budget:
    result = mid
    start = mid + 1
  else: end = mid - 1
print(result)