2512.예산

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

2512번: 예산

 

1.설명

문제에서 가능한 최대의 금액을 뽑아야하는 조건이 있습니다.따라서 리스트를 받고 나서 상한액을 점점 키우다가 만약 총 예산을 넘기면 그때 그 값의 -1 을 반환해야합니다. 상한액을 어떻게 키울까 하다가 이분탐색을 활용해 구했습니다. search 기법들은 나중에 한번에 정리해보겠습니다!!! 문제 자체는 이분 탐색(BInary search)이 어떻게 돌아가는지만 알면 문제 자체는 쉽게 풀 수 있었던거 같습니다. 매 탐색마다 예산과 money들을 비교하여 작은 것을 추가합니다.

 

2.코드

import sys

input=sys.stdin.readline
N=int(input())
money=list(map(int, input().split()))
M=int(input())
start,end=0,max(money)

while start<=end:
  mid=(start+end)//2
  current=0
  for i in money:
    if i >= mid:
      current+= mid
    else:
      current+=i
  if current <= M:
    start=mid+1
  else:
    end=mid-1
    
print(end)