[백준/Python] 2512번: 예산

Problem

---

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

2512번: 예산

Code

---

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
m = int(input()) 

prefix_sum=0
for i in arr:
    prefix_sum+=i

if prefix_sum<=m:
    print(max(arr))
else:
    start,end=0,max(arr)
    while start<=end:
        total=0
        mid=(start+end)//2
        for i in arr:
            if i>mid:
                total+=mid
            else:
                total+=i
        if total<=m:
            start=mid+1
        else:
            end=mid-1
    print(end)

Answer

---

각각의 합이 최대 예산보다 작으면 가장 큰 값을 출력한다.

그렇지 않을경우 이분탐색을 시작해서, 가능한 값중 최댓값을 출력하면 된다.

이분탐색의 최소값은 0, 최대값은 현재 값중 가장 큰 값이므로 max(arr)

가운데 값보다 값이 배열안에 값이 크면 전체 가격에 가운데 값을 더해주고,

아니라면  배열안의 값을 더해준다. 

그렇게해서 전체 값이 상한액보다 작다면 start를 가운데값보다 크게해서 반복하고

아니라면 end를 가운데값보다 작게해서 반복한다.