boj 2512 : 예산

문제 주소: https://www.acmicpc.net/problem/2512

난이도: silver 3

1.문제설명

• 예산을 분배하려한다.
• 하지만 이때 사용할수 있는 예산 총액이 있다.
• 따라서 정수 상한액을 설정해서, 이것보다 작으면 요구하는만큼 주고, 크면 상한액만큼 줄꺼다.
• 이때 배정된 예산들 중 최대값을 출력해라

2.문제해결 아이디어.

• 케이스를 두개로 나눠보자
  • 요구하는 금액의 총 합이, 예산 총액보다 적다 -> 요구하는 만큼 다 주면된다 -> 요구 금액 중 최대값 출력
  • 요구하는 금액의 총 합이, 예산 총액보다 크다 -> 상안액을 이분탐색으로 찾아서 최대값 찾아보자

3.문제접근법

#첫번째 케이스
if sum(requests) <= budget:
    return print(max(requests))

#두번째 케이스
low = 0 #이거를 min(requests)로 하면 틀린다
high = max(requests)
while low <= high:
    total = 0
    mid = (low + high) // 2
    for request in requests:
        if mid >= request:
            total += request
        else:
            total += mid
    if total > budget: #가능 지출보다 크면
        high = mid - 1 #상한을 낮춤
    else: #가능 지출보다 작으면
        low = mid + 1 #하한을 높힘
return print(high)

4.특별히 참고할 사항

• 문제 설명에 따라 유연하게 상한, 하한을 조절하는게 중요한거같다.
• 사실 이분탐색 문제는 정석이 정해져있다.
• 그리고 코테를 준비하며 읽은책에 의하면 면접등에서 이분탐색 구현을 시켰을 때 이를 완벽하게 할수 없는 사람이 많다고 한다.
• 자주쓰이고, 중요하니 외워두자

5.코드구현

N = int(input())
requests = list(map(int,input().split()))
budget = int(input())

def find_budget(requests, budget):
    if sum(requests) <= budget:
        return print(max(requests))
    else:
        low = 0
        high = max(requests)
        while low <= high:
            total = 0
            mid = (low + high) // 2
            for request in requests:
                if mid >= request:
                    total += request
                else:
                    total += mid
            if total > budget: #가능 지출보다 크면
                high = mid - 1
            else: #가능 지출보다 작으면
                low = mid + 1
        return print(high)

find_budget(requests, budget)