백준_2512_예산(이분 탐색)

https://www.acmicpc.net/problem/2512

2512번: 예산

해결 방법

> 이분 탐색을 이용한다.

> 처음 들어온 예산들의 합이 총 예산과 같으면 예산들 중 max를 출력한다.

> 같지 않다면 이분 탐색을 이용한다.

 

num = int(input())

_list = list(map(int, input().split()))

total = int(input())

 

if sum(_list) == total:

    print(max(_list))

else:

    low = 0

    high = max(_list)

    result = 0

    while low <= high:

        mid = (low + high) // 2

        tmp = 0

        for i in _list:

            tmp += min(i, mid)

        

        if tmp > total:

            high = mid - 1

        else:

            result = mid

            low = mid + 1

 

    print(result)