[softeer] [인증평가(4차) 기출] 슈퍼컴퓨터 클러스터 (python)

 

https://softeer.ai/practice/info.do?idx=1&eid=1204&sw_prbl_sbms_sn=83550 

Softeer

---

문제 회고

예산의 범위가 매우 커서 처음엔 하나씩 올려가면서 찾는 방식을 선택했더니 시간 오류가 났다. 이 전에 이진 탐색으로 큰 범위에서 되게 빠르게 풀어나가는 문제를 softeer에서 풀었었는데 혹시 여기도 적용이 될까 해서 풀어봤는데 바로 문제 없이 풀렸다... 

---

import sys

def check(mid):
    cost = 0
    for i in power:
        if mid > i:
            cost += (mid - i) ** 2
    if cost <= b:
        return True
    else:
        return False

def bsearch(start, end):
    if start == end:
        return start
    mid = (start + end + 1) // 2
    if check(mid):
        return bsearch(mid, end)
    else:
        return bsearch(start, mid - 1)

n, b = map(int, sys.stdin.readline().split())
power = list(map(int, sys.stdin.readline().split()))
power.sort()
min_power = power[0]
answer = bsearch(min_power, 2 * 10 ** 9)
print(answer)