[이진탐색/백준] 2512번 : 예산

- 문제 : https://www.acmicpc.net/problem/2512

 

여러 코테 불합격으로 코테가 많이 부족하다는 걸 알고 다시 알고리즘 풀이를 시작했다. 

문제를 많이 푸는 거에 집중하느라 제대로 이해를 못하거나 빠른 시간 안에 푸는 연습을 하지 않았는데, 이번에는 기초부터 이해하고 빠르게 푸는 연습을 하려고 한다. 

 

이 문제는 이진탐색 문제로, 주어진 국가 예산 안에서 최대로 분배할 예산을 정하는 문제이고, 지방 예산들을 가지고 이진탐색을 하는 로직이다. 

 

로직 

1. 최저 예산(left)을 0, 최대 예산(right)을 max(지방 예산들)로 설정한 뒤 while 문으로 이진 탐색을 진행한다.

1-1. while 문 탈출 조건은 left <= right로, 등호가 들어가야한다. 

2. 중간값인 mid와 지방 예산들을 비교해 최소값들의 합(total)을 구한다.

2-1. total 값과 국가 예산을 비교해 left 또는 right를 업데이트한다. 

2-2. 분배 예산(mid)을 늘려야하는 경우에는 해당 mid 값도 후보가 될 수 있으므로 result 값을 mid로 업데이트 한다.(result = mid)

3. while 문을 나왔을 때 result 값과 각 지방의 예산들 중 최소값을 구하고, 그 값들 중에서 최대값을 출력한다. 

 

 

 

- 정답 풀이 

n = int(input())
cities_budget = sorted(list(map(int, input().split())))
budget = int(input())

result = 0
left, right = 0, cities_budget[-1]
while left <= right : # 등호 빼먹으면 틀림
    mid = (left + right) // 2

    total = 0
    for i in range(n):
        total += min(cities_budget[i], mid) # 간결하게 표현하기 
    
    if total > budget:
        right = mid - 1
    else:
        result = mid # mid로 예산을 분배할 수 있을 때 result에 할당
        left = mid + 1
        
answer = 0    
for city in cities_budget:
    answer = max(answer, min(result, city))
    
print(answer)