백준 2512 – 예산

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번 구현

1. 초기 상한액 설정
   • 시작점(start): 최소한의 예산 상한액을 0 또는 지방 예산 요청의 최소값으로 설정할 수 있습니다.
   • 끝점(end): 최대한의 예산 상한액을 지방 예산 요청의 최댓값으로 설정합니다.
2. 이분 탐색 진행
   • start와 end 사이의 중간값(mid)을 상한액으로 가정하고, 모든 지방의 예산 요청에 대해 이 상한액을 적용하여 실제로 배정할 수 있는 총 예산액을 계산합니다.
   • 계산된 총 예산액이 주어진 국가 예산의 총액보다 크면, 상한액을 낮춰야 하므로 end를 mid - 1로 조정합니다.
   • 계산된 총 예산액이 주어진 국가 예산의 총액보다 작거나 같으면, 상한액을 높여도 될 여지가 있으므로 start를 mid + 1로 조정합니다.
3. 최적의 상한액 찾기
   • 이분 탐색을 통해 start가 end보다 커질 때까지 반복합니다. 탐색이 종료되면, end에 저장된 값이 모든 지방의 예산 요청을 만족시키면서 가능한 최대의 상한액이 됩니다.
4. 결과 출력
   • 최적의 상한액인 end 값을 출력합니다. 이 값은 모든 지방의 예산 요청을 주어진 총 예산 내에서 가능한 한 최대로 만족시키는 예산 분배의 기준이 됩니다.

3-1. 2512번 코드

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)