[백준] 예산

[백준] 예산_2512

[백준] 예산

예산

풀이

‘이분탐색’ (Binary Search) 기법을 이용해서 찾아야한다.
처음엔 그냥 while문으로 1씩 올려가면서 탐색했는데, 이렇게 하면 안된다.

생각해야할 점.
1) 지방 예산들을 모두 합했는데, 국가 예산보다 적은 경우
-> 전부 다 예산을 줄 수 있으므로 배열의 최댓값이 예산이다.
2) 지방 예산 중 가장 최소의 예산으로 합했는데, 국가 예산 보다 많은 경우
-> 모두 합했을 때, 국가 예산에 가까운 최댓값으로 나와야 한다.
3) 그 중간일 경우? -> 모두 합했을 때, 중간이하 값들은 원래 값으로 중간값 이상은 중간값을 쓴다.

생각할 때 막히는 부분
1) 이분 탐색에 대해서 생각을 못했다.
2) 최대 예산에 가장 가까운 값을 어떻게 선정해야하나 생각했다.
-> 가장 최대로 도달했을 때, min = mid가 된다.
3) 예산이 모두 같은 경우는 어떻게 해야할까 고민했다. -> 최소의 예산으로만 이루어졌기 때문에 따로 빼야했다.

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

if sum(data) <= m: # 모두 합했을 때, 예산보다 적은 경우
    print(max(data))

elif min(data) * n > m: # 가장 최소의 예산으로 이루어졌을 때, 예산이 적은 경우
    min, max = 1, min(data)
    result = 0
    while True:
        mid = (min + max) // 2
        
        if mid * n == m or min == mid:
            result = mid
            break
        elif mid * n > m:
            max = mid
        else:
            min = mid
    print(result)

else: # 최소 예산 이상 최대 예산 이하로 만들 수 있을 때, 예산이 많은 경우
    min, max = data[0], data[-1]
    result = 0
    while True:
        mid = (min + max) // 2
        ans = 0
        for i in data:
            if i <= mid:
                ans += i
            else:
                ans += mid
        
        if ans == m or min == mid:
            result = mid
            break
        elif ans > m:
            max = mid
        else:
            min = mid
    print(result)