[Python] softeer.ai 슈퍼컴퓨터 클러스터

import sys
input = sys.stdin.readline

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):
    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)

#left는 업그레이드 비용이 절대로 B를 넘지 않는다.

#right는 업그레디으 비용이 절대로 B 아래가 되지 않는다.

#때문에 right-left=1 이라는 것은 B를 넘지 않는 최대 효율이 left라는 것이다.

 

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

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