[Softeer] S1204 슈퍼컴퓨터 클러스터

[Softeer]

Question

Language: Python

해당 문제는 주어진 예산을 기반으로 클러스터를 구성하는 컴퓨터의 성능을 업그레이드 해서 최소 성능을 가지는 컴퓨터의 성능을 최대화하는 것이 목표이다. 하지만, 예산의 크기가 10¹⁸으로 매우 크기 때문에 O(n)의 풀이로는 해결할 수 없다.

이런 유형의 문제의 경우 대부분 binary search을 활용하여 문제를 풀이할 수 있다.

결국, 예산 = 업그레이드 할 수 있는 성능으로 볼 수 있기 때문에 최대 업그레이드 가능 값은 예산으로 설정해서 이진탐색을 통해 최대로 갖출수 있는 최소 성능 값을 구한다.

Solution

import sys
def solution():
    start,end=0,10**18
    maximum_minimal_performance=0
    while start <= end:
        mid=(start+end)//2
        cost=0
        #최소 성능을 mid으로 맞추기 위해 필요한 비용을 계사한다.
        for number in numbers:
            cost+=max(mid-number,0)**2
        #예산 내에 업그레이드가 가능한 경우 성능값을 높인다.
        if cost <= b:
            maximum_minimal_performance=max(maximum_minimal_performance,mid)
            start=mid+1
        #예산을 넘어서는 경우 성능값을 낮춘다.
        else:
            end=mid-1
    
    print(maximum_minimal_performance)

if __name__ == "__main__":
    n,b=map(int,sys.stdin.readline().split())
    numbers=list(map(int,sys.stdin.readline().split()))
    solution()