[백준] 2512 - 예산 (Python)

문제 출처 :

www.acmicpc.net/problem/2512

2512번: 예산

문제 풀이 :

• 특정값을 찾을때까지 이분 탐색을 계속 시행하면 된다.
• 이경우엔 우리가 정하고 있는 어떤 값 보다 예산이 많으면 그 값만큼으로 짜른다는 조건이 있는데 이부분만 잘 처리해주면 정답을 쉽게 구할 수 있다.
• 원리에 대해서 생각해보면 가장 작은 예산인 1원을 left로 두고 주어진 값중에 가장 큰 값인 max값을 right두고 탐색을 시작한다.
  • 기준값을 토대로 예산을 정한뒤에 계산된 예산이 더 크다면 기준값을 낮춰서 계산되는 예산을 줄여주고
  • 계산된 예산이 더 작으면 기준값을 높여서 계산되는 예산을 높여준다.

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

left = 1
right = max(arr)
max_val = 0
while(left<=right):
    mid = (left+right)//2
    res=0
    for i in arr:
        if(i<=mid):
            res+=i
        else:
            res+=mid

    if(res>m):
        right = mid-1
    if(res<=m):
        left = mid+1

print(right)