[백준] 2512번 예산

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

이진 탐색을 이용해서 풀었고, 이코테의 이진탐색 챕터의 떡볶이 떡 만들기와 비슷해서 금방 풀 수 있었던 문제였다.

# 2512 : 예산

import sys
input = sys.stdin.readline

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

start = 0
end = max(request)

result = 0  # 상한액
while start <= end:
    total = 0
    mid = (start + end) // 2

    for x in request:
        # 요청한 예산이 상한액보다 크거나 같을 경우
        if x >= mid:
            total += mid
        # 요청한 예산이 상한액보다 작을 경우
        else:
            total += x
    # 예산이 충분할 경우
    if total <= m:
            result = mid
            start = mid + 1
    # 예산 넘을 경우
    else:
        end = mid - 1

print(result)

Uploaded by Notion2Tistory v1.1.0