백준 문제풀이 - 2512 번

링크 -> https://www.acmicpc.net/problem/2512

1. 요약 및 풀이방법

여러 지방의 예산 요청을 받아 총 사용 가능한 예산 중 가능한 최대의 예산을 배정하는 방법을 찾는 문제입니다.

최소 예산(1)과 요청 받은 최대 예산을 범위로 이분 탐색 알고리즘을 적용했습니다.
mid를 기준으로
mid보다 작은 예산 요청은 그대로,
mid보다 큰 예산 요청은 mid 값으로 처리하고,

이렇게 배정했을 때,
총 가용한 예산보다 적으면 예산을 키우기 위해 start 값을 mid + 1로,
총 가용한 예산보다 크면 예산을 줄이기 위해 end 값을 mid - 1 로 변경하며 이분 탐색 하였습니다.

2. Code

def main():
    N = int(input())
    budgets = list(map(int, input().split()))
    total = int(input())

    start = 1
    end = max(budgets)
    assigned = []
    while start <= end:
        mid = (start + end) // 2

        temp = []
        for budget in budgets:
            if budget < mid:
                temp.append(budget)
            else:
                temp.append(mid)

        if sum(temp) <= total:
            assigned = temp
            start = mid + 1
        else:
            end = mid - 1

    print(max(assigned))

if __name__ == "__main__":
    main()

3. 학습 내용

처음에 start 값을 N으로 세팅했습니다.
왜냐하면 가용한 총 예산(total) 값의 범위가 [N ~ 1,000,000,000] 이었기 때문입니다.
이때, 각 요청 예산이 N보다 작은 경우 아예 예선 배정을 할 수 없는 예외가 생겨 start 값을 1로 설정하였습니다.

또한 start값을 요청 예산들 중 min 값을 적용해도 예외가 발생합니다.
min값보다 적게 배정해야 하는 경우도 있기 때문입니다.
예외)

4
2 2 2 2
7

4. 결과