문제 링크
문제 풀이
- 예산 요청 금액이 예산보다 작거나 같으면(i <= mid) 예산 요청 금액 만큼의 예산을 받을 수 있고, 예산보다 크면(i > mid) 예산 만큼의 예산을 받을 수 있는데, 이는 for문을 이용해서 작성할 수 있다.
- 이에 따른 총 예산의 합이 M보다 크면(total > m) 예산을 초과하게 되므로 배정할 수 있는 예산의 크기를 줄여야 한다. 반대로 M보다 작거나 같으면(total <= m) 다시 예산의 크기를 늘려야 한다.
- 또한, 배정할 수 있는 예산은 각 예산 요청의 최댓값보다 클 수 없으므로 초기 end 값은 입력 받은 리스트의 최댓값이 된다.
전체 코드
import sys
n = int(sys.stdin.readline())
l = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
start = 0
end = max(l)
res = 0
while start <= end:
total = 0
mid = (start + end) // 2
# mid가 예산일 때의 총 예산 계산
for i in l:
if i <= mid:
total += i
else:
total += mid
# 총 예산은 M보다 클 수 없으므로 예산 재계산
if total > m:
end = mid - 1
else:
# 현재의 예산과 비교하여 더 큰 값 저장
res = max(res, mid)
start = mid + 1
print(res)
반응형
'Coding Test > BOJ' 카테고리의 다른 글
[백준/Python] 10026 적록색약 (0) | 2024.02.15 |
---|---|
[백준/Python] 12904 A와 B (2) | 2024.02.14 |
[백준/Python] 2565 전깃줄 (2) | 2024.02.13 |
[백준/Python] 13335 트럭 (2) | 2024.02.12 |
[백준/Python] 7576 토마토 (0) | 2024.02.09 |