[백준]2512번: 예산

https://www.acmicpc.net/problem/2512

2512번: 예산

---

(지방별 요청예산 중 최댓값)*N 의 값이 총 예산 M보다 같거나 큰 경우에는 예산을 각 지방이 요청한 대로 배정해주면 되지만,

그렇지 않은 경우는 상한액을 배정해주어야 한다.

 

간단하게는 선형탐색을 생각할 수 있었는데,

주어진 m의 범위가 1부터 1,000,000,000 사이라는 점이 걸렸다.

문제에서의 제한시간은 1초이고, 파이썬은 1초동안 약 2000만 번의 연산을 수행한다.

따라서 선형탐색을 하면 시간초과가 나게 된다.

 

그래서 시간복잡도가 logN인 이진탐색을 쓰기로 했다.

---

각 지방이 요청한 예산값은 배열 requests에 저장했다.

 

상한선이 x일 때 지급되는 총 예산 계산하기

def budget(x):
  result=0
  for i in range(n):
    if x>=requests[i]:
      result += requests[i]
    else:
      result += x
  return result

 -지방에서 요청한 비용이 상한액보다 크거나 같은 경우, result에 상한액을 더해준다

 -그렇지 않은 경우, result에 지방에서 요청한 비용을 더해준다

 -result를 리턴한다

---

상한선 x 결정하기

start = 0
end = max(requests)

result = 0
while start <= end:
  mid = (start+end)//2
  if budget(mid)<=m:
    result=mid
    start=mid+1
  else:
    end=mid-1

print(result)

 -시작점:0, 끝점: 요청 금액 중 최댓값

 -상한선이 m일 때 지급되는 총 예산이 M보다 작으면, result에 m을 저장 후 m보다 큰 범위를 탐색

 -상한선이 m일 때 지급되는 총 예산이 M을 넘어가면, m보다 작은 범위를 탐색

 

---

전체 코드

import sys
input = sys.stdin.readline

#상한선 x일 때 총 지급 예산 계산
def budget(x):
  result = 0
  for i in range(n):
    if x >= requests[i]:
      result += requests[i]
    else:
      result += x
  return result

#입력받기
n = int(input())
requests = list(map(int,input().split()))
m = int(input())

#예산이 충분하여 각 지방에서 요청한대로 지급할 수 있는 경우
if max(requests)*n <= m:
  print(max(requests))
  exit()

    
#binary search로 가장 큰 상한액 찾기
result = 0
start=0
end=max(requests)

while start <= end:
  mid = (start+end)//2
  if budget(mid) <= m:
    result = mid
    start = mid+1
  else:
    end = mid-1

print(result)