Algorithm

[ BOJ ] 백준 2512 - 예산(파이썬 문제 풀이)

j-y 2021. 3. 14. 01:03
반응형

문제 링크

 

2512번: 예산

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

www.acmicpc.net

 

이분 탐색으로 풀 수 있는 예산 문제 입니다.

가능한 예산 중 최대값을 찾기위해 시작 값, 끝 값을 나누어 중간 값으로 범위를 확장, 축소하여 문제를 풀이했습니다.

 

문제 풀이(파이썬)

N = int(input())
req = list(map(int, input().split()))
M = int(input())

lt = 1
rt = max(req)
res = 0
while lt <= rt:
    mid = (lt+rt)//2

    res_tmp = 0
    for r in req:
        if r > mid:
            res_tmp += mid
        else:
            res_tmp += r

    if res_tmp > M:
        rt = mid-1
    else:
        res = mid
        lt = mid+1

print(res)
반응형