9주차_#2512 예산

💬문제 이해

핵심) 공통의 상한액을 구한뒤, 정해진 총액 이하에서 가능한 한 최대의 총 예산 구하기.

• 다음 방법으로 배정
  1) 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.
  2) 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여, 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다.
  

예시
전체 국가예산이 485
4개 지방의 예산요청이 각각 120, 110, 140, 150

상한액을 127로 잡으면, 위의 요청들에 대해서 각각 120, 110, 127, 127을 배정하고
그 합이 484로 가능한 최대가 된다.

입력 조건
첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 100,000 이하이다. 그 다음 줄에는 총 예산을 나타내는 정수 M이 주어진다. M은 N 이상 1,000,000,000 이하이다.

입력예시
4
120 110 140 150
485
출력예시
127

💡 처음 든 생각

1.'원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제이고,
2. 가능한 예산의 범위는 1,000,000,000 겁나게 크니까
Parametic Search를 활용할 수 있겠다!

관련 활용 예제로 떡볶이떡썰기 가 있었다.

📝 해결 스케치

이런식으로 이진탐색으로 최적 상한액을 찾아나가면 되겠구만!

• 최적 상한액 이하인 경우 : 그대로 예산 합에 반영
• 최적 상한액 이상인 경우 : 상한액을 예산 합에 반영

이 예산 합이 주어진 예산합보다 작거나 같되, 최대의 값을 가져아한다!

처음 짠 코드

# 데이터 입력
n = int(input())
departments = list(map(int, input().split()))
budget = int(input())


# 상한액을 찾는 이진탐색
def binary_search(array, start, mid, end) :
  while (start <= end) :
    total = 0
    mid = (start+end) // 2
    for x in array :
      # 상한액을 정했을때 총 예산 계산
      if x > mid :
        total += x - mid
      if total < m :
        end = mid - 1
      else :
        result = mid
        start = mid + 1
  return result

# 상한액을 바탕으로 최종 예산 계산
def calc_budget(upper_limit, departments) :
  total_budget = 0
  for i in departments :
    if i > upper_limit :
      total_budget += upper_limit
    else :
      total_budget += i
  return total_budget



# 모든 요청이 배정될 수 있는 경우 그대로 출력하고 끝남
departments_add = sum(departments)
if departments_add <= budget :
  print(departments_add)
else :
  # 이진탐색 준비
  start = 0
  end = max(departments)
  mid = (start+end)//2
  # 상한액 이진탐색으로 구하기
  upper_limit = binary_search(departments, start, mid, end) 
  # 상한액을 바탕으로 최종 예산 계산
  res = calc_budget(upper_limit, departments) 
  print(res)