<aside> 🔥 백준 2512번 문제 링크

</aside>

<aside> 🔥 문제 정리

n = 지방의 수

n개의 지방에서 요청하는 예산 요청 금액

m = 예산의 총액

국가에서 지방이 예산요청을 하면 다음과 같은 조건으로 가능한 한 최대로 예산을 배정하려고한다.

1. 모든 요청이 배정될 수 있는 경우 요청한 금액 그대로 배정

2. 모든 요청이 배정될 수 없는 경우 특정 정수 상한액을 계산하여 그 이상인 경우 상한액으로 배정.

   그 이하인 경우는 요청 금액 그대로 배정.

출력은 예산의 상한액이 지정될 경우 상한액을 출력해야한다.

# 입력값
4
120 110 140 150
485

# 출력값
127

# 설명
140 150이 상한액보다 크므로 최종 예산 분할은 120 110 127 127이 된다.

</aside>

<aside> 🔥 접근 방법

예산의 범위는 0 ~ 최대 요청액으로 정해놓는다.

위 범위에서 중간을 상한액으로 잡고 지방의 예산 요청 리스트를 순회하며 상한액보다 큰 경우에는

상한액으로 예산을 할당해서 총 예산을 계산한다.

이때 계산한 총 예산이 원래 지정했던 총액보다 작을 경우에는 상한액을 높히기 위해 오른쪽으로 탐색.

반대로 계산된 총 예산이 원래 지정했던 총액보다 클 경우 왼쪽으로 탐색을 한다.

</aside>

<aside> 🔥 코드 진행

(1) 입력값을 받아오고 예산의 범위를 0 ~ 요청 리스트 중 가장 큰 값으로 지정한다.

import sys

def input():
    return sys.stdin.readline().strip()

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

lo = 0  # 0 부터
hi = max(li)  # 리스트에서 가장 큰값

(2) 예산의 범위를 뛰어넘지 않는 경우에 반복한다.

계산된 예산의 총액을 담을 total을 지정하고 중간값을 찾는다.

while lo <= hi:
    total = 0  # 예산의 총 양
    mid = (lo + hi) // 2  # 중간 값

(3) 전체 리스트를 순회하며 상한액보다 큰 경우에는 상한액으로 지정하여 total에 추가한다.

while lo <= hi:
    total = 0  # 예산의 총 양
    mid = (lo + hi) // 2  # 중간 값

    for x in li:
        if x >= mid:
            total += mid
        else:
            total += x

(4) 계산된 총액이 할당된 총액보다 작거나 같을 경우에는 상한액을 높혀간다 (오른쪽 탐색)

반대로 클 경우에는 상한액을 낮춰간다. (왼쪽 탐색)

if total <= m:
        lo = mid + 1
    else:
        hi = mid - 1

그림으로 그려본 알고리즘

</aside>