https://www.acmicpc.net/problem/2512
input :
-
지방의 수 N (3 <= N <= 10,000)
-
예산 요청 Ki (1 <= Ki <= 100,000)
-
총 예산 M (N <= M <= 1,000,000,000
output : -
배정된 예산들 중 최댓값
조건 : -
모든 요청이 가능 한 경우에는 요청한 금액을 그대로 배정한다.
-
모든 요청이 가능하지 않을 땐, 특정한 정수 상한액을 계산 그 이상에는 모두 상한액을 배정, 이하에는 요청한 금액을 그대로 배정
띠용쓰 띠용..
이번엔 지방의 예산 요청에 집중하는 것ㅇ이 아닌.
최대 예산을 어떻게 지정할 까에 집중해야 한다. 수많은 범위중에 하나를 지정 하는 것인데 순차적으로 할 경우 시간 복잡도에의 해 바로 실패 되므로 당연히 이진탐색을 사용한다.
이진 탐색시에 반복문의 조건. start > end 일때 종료 된다.
while start <= end 이면 계속 반복 하도록.
start 와 end 값들이 업데이트 되어야 하는데 왜>?
mid + 1 이나 mid - 1이 되는 가??
이미 mid 값은 확인을 하였다. 그래서 우리으 탐색범위에서 벗어나는 것이다.
정답 코드 :
import sys
N = int(sys.stdin.readline())
money = list(map(int, sys.stdin.readline().split()))
max_pivot = int(sys.stdin.readline())
low = 0
high = max(money)
while low <= high:
mid = (low + high) // 2
sum = 0
for i in money:
if i > mid:
sum += mid
else: sum += i
if sum > max_pivot: high = mid - 1
else: low = mid + 1
print(high)
내가 필요한 정답이 high 일수도 있고 mid일 수도 있다.
마지막 계산 될때 어떤 값이 필요한지 잘 생각해보자
