문제

' 2512번 예산 '
https://www.acmicpc.net/problem/2512

Check point

📌 이진 탐색/ 이분 탐색/ binary search

• 자료의 중앙에 있는 원소를 고른다.
• 중앙 원소의 값과 찾고자 하는 목표 값을 비교한다.
• 목표 값이 중앙 원소의 값보다 작으면 자료의 왼쪽 반에 대해서 새로 검색을 수행하고, 크다면 자료의 오른쪽 반에 대해서 새로 검색을 수행한다.
• 찾고자 하는 값을 찾을 때까지 위의 과정을 반복한다.

기본 코드

💡 반복문 사용

def binary(arr, key):
    start, end = 0, len(arr) - 1
    while start <= end:
        middle = (start + end) // 2
        if arr[middle] == key:  # 검색 성공
            return True
        elif arr[middle] > key:
            end = middle - 1
        else:
            start = middle + 1
    return False  # 검색 실패

💡 재귀 사용

def binary(arr, start, end, key):
    if start > end:  # 검색 실패
        return False
    else:
        middle = (start + end) // 2
        if arr[middle] == key:  # 검색 성공
            return True
        elif arr[middle] > key:
            binary(arr, start, middle - 1, key)
        elif arr[middle] < key:
            binary(arr, middle + 1, end, key)

📌 문제 조건

• 정해진 총액 이하에서 가능한 한 최대의 총 예산을 구해야 하므로 total <= M 을 고려해야 한다.

코드

python

💡 반복문 사용

N = int(input())
lst = list(map(int, input().split()))
M = int(input())
result = 0  # 출력해야 하는 최대 예산
start, end = 1, max(lst)  # 1을 시작, 최댓값을 끝
while start <= end:
    mid = (start + end) // 2  # 중앙 원소 고르기
    total = 0  # 예산의 합
    for l in lst:
        if l > mid:
            total += mid
        else:
            total += l
    if total <= M:  # M 이하 이면 중앙값+1 ~ 끝 값 다시 찾기
        result = mid
        start = mid + 1
    else:  # M초과 이면 시작 ~ 중앙값-1 값 다시 찾기
        end = mid - 1
print(result)

다른 방법

💡 재귀 사용

def binary(lst, start, end, M):
    global result
    if start > end:  # 검색 실패
        return
    else:
        mid = (start + end) // 2  # 중앙 원소 고르기
        total = 0  # 예산의 합
        for l in lst:
            if l > mid:
                total += mid
            else:
                total += l
        if total <= M:  # M 이하 이면 중앙값+1 ~ 끝 값 다시 찾기
            result = mid
            return binary(lst, mid + 1, end, M)
        else:
            return binary(lst, start, mid - 1, M)


N = int(input())
lst = list(map(int, input().split()))
M = int(input())
start, end = 1, max(lst)  # 1을 시작, 최댓값을 끝
result = 0  # 출력해야 하는 최대 예산
binary(lst, start, end, M)
print(result)