[백준] 2512 예산

📌문제 링크

2512 예산

💡문제 풀이

책에서 본 떡볶이 떡 만들기 문제랑 비슷한 것 같다
백준에서는 2805 나무 자르기, 1654 랜선 자르기 문제와 유사함!

정민언니가 알려준 방법으로 알고리즘을 생각해봤어요

1. 구해야 하는 것 : 정해진 총액 이하에서 줄 수 있는 가능한 한 최대의 예산 (한 부서당 예산 상한액)
   -> start = 0, end = 최대 예산요청 금액
2. 1번을 구하는 데 필요한 기준 : 상한액에 따른 부서별 배정 예산 총액

📋코드

# 2512 예산
import sys
n = int(input())
arr = list(map(int, sys.stdin.readline().split()))
m = int(input())

# 이진 탐색을 위한 시작점과 끝점 설정
start = 0
end = max(arr)

result = 0
while start <= end:
    total = 0
    mid = (start + end) // 2
    for x in arr:
        # 예산 총액 계산
        if x > mid:
            total += mid
        else:
            total += x
    # 예산이 부족한 경우 상한액 낮춤
    if total > m:
        end = mid - 1
    # 예산이 남는 경우 상한액 높임
    else:
        result = mid
        start = mid + 1

print(result)

한 번에 통과 완!!ㅎㅎ