CS/Algorithm
[BOJ/Python] 백준 2512번 - 예산
sohy
2022. 8. 3. 20:08
백준 #2512 예산
2512번: 예산
첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상
www.acmicpc.net
import sys
input = sys.stdin.readline
n = int(input()) # 지방의 수
reqs = list((map(int, input().split()))) # 각 지방의 예산 요청
m = int(input()) # 총 예산
left = 0
right = max(reqs)
while left <= right:
mid = (left + right) // 2 # 상한액
req_sum = 0
for req in reqs:
if req > mid: # 요청액이 상한액보다 클 경우 상한액으로 계산
req_sum += mid
else: # 요청액이 상한액보다 작을 경우 요청액으로 계산
req_sum += req
if req_sum > m: # 요청액 합이 총 예산보다 클 경우
right = mid - 1
else:
left = mid + 1
print(right)
이분 탐색 방법을 활용한다!
- left와 right는 요청 가능한 금액의 범위를 의미한다. left의 초깃값은 0, right의 초깃값은 요청액의 최댓값으로 한다.
- 상한액(mid)은 left와 right의 중간값으로 한다.
- 요청액이 상한액보다 클 경우 상한액으로, 작을 경우 요청액으로 하여 각 요청들에 대한 전체 합을 구한다.
- 전체 합이 총 예산보다 클 경우 right를 중간값 - 1로, 작을 경우 left를 중간값 + 1로 한다. (값이 크면 값을 줄여야 하니까 범위의 최댓값인 right 값을 줄이고, 값이 작으면 값이 커져야 하니까 범위의 최솟값인 left 값을 높이는 것!)
- 탐색을 반복하다 left 값이 right 값보다 커졌을 때 반복을 중단한다.
- 범위의 최댓값인 right 값이 예산들 중 최댓값이 된다.
