Python을 이용한 2512번 : 예산에 대해서 포스팅하겠습니다. 2512번은 이분 탐색, 매개 변수 탐색으로 분류되는 문제입니다.
1. 2512번 문제설명
- 입력:
- 첫째 줄: 지방의 수 N (3 ≤ N ≤ 10,000)
- 둘째 줄: 각 지방의 예산 요청을 나타내는 N개의 정수 (각 값은 1 이상 100,000 이하)
- 셋째 줄: 국가 예산의 총액 M ( N 이상 1,000,000,000 이하)
- 목표:
- 주어진 국가 예산 내에서 모든 지방의 예산 요청을 만족시킬 수 있는 상한액을 설정하고, 이 상한액을 적용하여 배분했을 때의 예산들 중 최댓값을 출력합니다.
- 출력:
- 배정된 예산들 중 최댓값을 나타내는 정수를 첫째 줄에 출력
2. 2512번 접근방법
- 이 문제에서 중요한 것은 총 예산액 내에서 가능한 한 많은 요청을 만족시키는 것이므로, 이분 탐색 과정에서 총 예산액을 초과하지 않는 선에서 최대한의 상한액을 찾는 것입니다.
- 이분 탐색을 사용함으로써, O(NlogM)의 시간 복잡도로 문제를 해결할 수 있으며, 이는 대부분의 입력 크기에 대해 충분히 효율적입니다.
3. 2512번 구현
- 초기 상한액 설정
- 시작점(
start
): 최소한의 예산 상한액을 0 또는 지방 예산 요청의 최소값으로 설정할 수 있습니다. - 끝점(
end
): 최대한의 예산 상한액을 지방 예산 요청의 최댓값으로 설정합니다.
- 시작점(
- 이분 탐색 진행
start
와end
사이의 중간값(mid
)을 상한액으로 가정하고, 모든 지방의 예산 요청에 대해 이 상한액을 적용하여 실제로 배정할 수 있는 총 예산액을 계산합니다.- 계산된 총 예산액이 주어진 국가 예산의 총액보다 크면, 상한액을 낮춰야 하므로
end
를mid - 1
로 조정합니다. - 계산된 총 예산액이 주어진 국가 예산의 총액보다 작거나 같으면, 상한액을 높여도 될 여지가 있으므로
start
를mid + 1
로 조정합니다.
- 최적의 상한액 찾기
- 이분 탐색을 통해
start
가end
보다 커질 때까지 반복합니다. 탐색이 종료되면,end
에 저장된 값이 모든 지방의 예산 요청을 만족시키면서 가능한 최대의 상한액이 됩니다.
- 이분 탐색을 통해
- 결과 출력
- 최적의 상한액인
end
값을 출력합니다. 이 값은 모든 지방의 예산 요청을 주어진 총 예산 내에서 가능한 한 최대로 만족시키는 예산 분배의 기준이 됩니다.
- 최적의 상한액인
3-1. 2512번 코드
Python
from sys import stdin
# 입력 처리
n = int(stdin.readline()) # 지방의 수
budgets = list(map(int, stdin.readline().split())) # 각 지방의 예산 요청
total_limit = int(stdin.readline()) # 총 예산
# 이진 탐색을 위한 시작점과 끝점 설정
start, end = 0, max(budgets)
# 이진 탐색 시작
while start <= end:
mid = (start + end) // 2 # 중간값 계산. 예산 상한선을 의미합니다.
total = 0 # 필요한 총 예산을 계산할 변수 초기화
# 각 지방별 예산 요청을 확인하여 총 예산 계산
for budget in budgets:
# 현재 예산 요청이 상한액(mid)보다 큰 경우
if budget > mid:
total += mid # 상한액만큼만 예산을 배정합니다. 이는 예산이 상한액을 초과하는 지방에 대해 상한액을 적용하는 과정입니다.
else:
total += budget # 예산 요청이 상한액 이하인 경우 요청한 예산 그대로 배정합니다.
# 총 예산이 총 예산 한도를 초과하는 경우
if total > total_limit:
end = mid - 1 # 상한액을 낮춥니다. 총 예산이 한도를 초과했으므로 상한액을 줄여 총 예산을 줄여야 합니다.
else:
start = mid + 1 # 상한액을 높입니다. 총 예산이 한도 이하인 경우 상한액을 높여 더 많은 예산을 배정할 수 있는 여지를 늘립니다.
# 최적의 상한액 출력
# 이분 탐색의 결과, end는 최대 예산 상한액이 됩니다. 이는 while 반복문의 조건으로 인해 start가 end를 초과하는 순간 end에 저장된 값이
# 모든 지방의 예산 요청을 만족시키면서도 총 예산 한도 내에서 가능한 최대 상한액임을 의미합니다.
print(end)