문제풀이/백준
2512 - 예산
동바리
2023. 9. 2. 18:09
2512번: 예산
첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상
www.acmicpc.net
코드 :
import sys
input = sys.stdin.readline
N = int(input())
member = list(map(int, input().split()))
total_money = int(input())
start = 0
end = max(member)
mid = 0
mid_val = 0
while (start <= end):
mid = int((start + end) / 2)
sum = 0
for i in range(0, len(member)):
sum += min(member[i], mid)
if (sum > total_money):
end = mid - 1
else:
start = mid + 1
mid_val = max(mid_val, mid)
#print(mid_val)
print(mid_val)
- 상한선을 잘 선택해야 풀 수 있는 문제였습니다.
- 상한선 선택은 이진탐색으로 진행합니다.
- 상한선을 선택했다면 min 함수를 이용해 지방에게 줄 돈을 선정합니다.
- 만일 상한선보다 작은 요청금액이라면 요청금액대로 줄 것이고, 상한선보다 큰 요청금액이라면 상한선만큼 줍니다. 이 때 내어준 총 금액은 sum 변수에 저장합니다.
- sum 변수가 줄 수 있는 금액보다 크다면 배제합니다.
- sum 변수가 줄 수 있는 금액보다 크거나 작다면 해당 상한선을 저장하고, 이 상한선보다 더 큰 상한선이 있는지 mid를 조정하며 찾습니다.