Python/백준

[백준 파이썬] 2512번 예산

AI 꿈나무 2021. 5. 2. 13:58
반응형

백준 2512번 예산

www.acmicpc.net/problem/2512

 

2512번: 예산

첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상

www.acmicpc.net

 

파이썬 풀이

import sys
input = sys.stdin.readline

N = int(input())
cities = list(map(int, input().split()))
budgets = int(input()) # 예산
start, end = 0, max(cities) # 시작 점, 끝 점

# 이분 탐색
while start <= end:
    mid = (start+end) // 2
    total = 0 # 총 지출 양
    for i in cities:
        if i > mid:
            total += mid
        else:
            total += i
    if total <= budgets: # 지출 양이 예산 보다 작으면
        start = mid + 1
    else: # 지출 양이 예산 보다 크면
        end = mid - 1
print(end)
반응형