[BOJ] [Python] 2512번 : 예산

이진탐색을 이용하여 풀었다.

 

low는 0으로, high는 예산의 최댓값으로 잡았다.

 

n = int(input())
region_p = sorted(list(map(int, input().split())))
max_p = int(input())


def BSearch(r_p, m_p):
    low = 0
    high = r_p[-1]
    result = 0

    while low <= high:
        mid = (low + high) // 2
        hap = 0

        for i in region_p:
            hap += min(i, mid)

        if hap == m_p:
            return mid

        elif hap > m_p:
            high = mid - 1

        else:
            result = mid
            low = mid + 1

    return result
print(BSearch(region_p, max_p))

 

 

 

return을 하나만 작성할 경우, 이렇게도 가능하다.

 

n = int(input())
region_p = sorted(list(map(int, input().split())))
max_p = int(input())


def BSearch(r_p, m_p):
    low = 0
    high = r_p[-1]
    result = 0

    while low <= high:
        mid = (low + high) // 2
        hap = 0

        for i in region_p:
            hap += min(i, mid)

        if hap <= m_p:
            result = mid
            low = mid + 1

        else:
            high = mid - 1

    return result

print(BSearch(region_p, max_p))