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

문제 : 

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

Softeer

풀이 내용:

softeer 측에서 제공해주는 풀이도 있다. 

나의 경우에는
1) dict에 key: 성능 value: 해당 성능을 가지는 컴퓨터의 갯수 를 저장 한 뒤에 
2) 이분탐색을 사용해서 mid 값이 우리가 원하는 최적의 값이라고 가정 한 뒤 이분탐색을 실행 해서 풀었다.

cf) 주의해야할 점이 나의 경우 이분 탐색에서 right(최댓값)에 대해서 B+1로 생각하고 풀어서 좀 틀렸었는데 이분 탐색 내에서 left right mid 가 가지는 의미는 성능이므로 right를 해 줄 때 B의 예산으로 최대가 될 수 있는 값을 넣어주어야 한다.

 

n,b = map(int,input().split())
num_list= list(map(int,input().split()))
num_dict = {}

num_list = sorted(num_list,reverse=True)
left= num_list[-1]
right = 2000000000

for i in num_list:
    if(i not in num_dict.keys()):
        num_dict[i]=1
    else:
        num_dict[i]+=1



while(right-left>1):
    #left는 업그레이드 비용이 절대로 B를 넘지 않는다.
    #right는 업그레디으 비용이 절대로 B 아래가 되지 않는다.
    #때문에 right-left=1 이라는 것은 B를 넘지 않는 최대 효율이 left라는 것이다.
    mid = (right+left)//2
    cur_cost = 0
    isLeft = 1
    for k,v in num_dict.items():
        if(k<mid):
            cur_cost +=  ((mid-k)**2)*v
            if(cur_cost>b):
                right = mid
                isLeft=0
                break
    if(isLeft):
        left=mid

print(left)