[이진/이분탐색] 백준 2512 예산 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

2512번: 예산

 

 

 

2. 문제 풀이

 제한된 예산 내에서, 줄 수 있는 최대의 예산을 구하는 문제입니다.

 

2022.02.10 - [Algorithm] - [정렬/탐색] 백준 2805 나무 자르기 - Python

[정렬/탐색] 백준 2805 나무 자르기 - Python

 언뜻보면 그리디 문제같지만, 사실 이진탐색(Binary Search) 문제입니다. 남는 예산이 없도록 최대 예산액을 '이진 탐색'으로 찾아냅니다.

 백준 2805 나무 자르기 문제와 비슷하며, 최대 나무길이가 최대 예산액으로 바뀐 것뿐입니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

# 입력
N = int(input())
budget = list(map(int, input().split()))
total_budget = int(input())

# 이진탐색
budget.sort()  # 오름차순 정렬
start, end = 1, budget[-1]  # 예산의 최소, 최댓값
while start <= end:
    mid = (start+end)//2  # 예산 제한
    cost = 0  # 비용
    for i in budget:
        if i > mid:  # 예산보다 더 많으면 잘림
            cost += mid
        else:
            cost += i

    # 총 예산보다 크면, 최대 예산액을 줄임
    if cost > total_budget:
        end = mid - 1

    # 총 예산이 남으면, 최대 예산액을 늘림
    else:
        start = mid + 1
print(end)

 총 예산을 초과하면 줄이고, 예산이 남으면 늘리면서 '상한액'을 탐색합니다. 탐색을 진행할 때마다, 탐색 범위가 절반씩 줄어듭니다. 

 

2022.02.09 - [Algorithm] - [Algorithm] 이진탐색(Binary Search), 반반 나누어서 찾자

[Algorithm] 이진탐색(Binary Search), 반반 나누어서 찾자

 이진탐색에 대한 설명과 코드는 위 글에서 보실 수 있습니다.