[Softeer] HSAT 4회 기출 - 슈퍼컴퓨터 클러스터

문제

<배경>

대규모 머신 러닝에서는 여러 컴퓨터를 하나의 클러스터로 묶어 계산을 수행하는 경우가 많다.

병렬 컴퓨팅 파워가 늘어나면 훨씬 더 거대한 데이터도 실용적으로 사용할 수 있게 된다.

클라우드 컴퓨팅을 이용하는 기업도 많지만, 개인정보와 보안, 네트워킹, 비용 등의 문제로 직접 클러스터를 구축하는 경우도 많다.

 

현지도 이러한 머신 러닝용 클러스터를 관리하는 역할을 맡고 있다.

클러스터의 성능은 컴퓨터의 수가 많아질 수록, 각각의 성능이 올라갈 수록 향상된다.

그런데 어느 날 협업 중인 몇몇 연구실에서 클러스터의 성능을 업그레이드해 달라는 요청을 보내 왔다.

이들은 특히 클러스터를 이루는 각각의 컴퓨터 중 성능이 가장 낮은 컴퓨터의 성능이 병목이 된다고 알려 왔다.

 

이 클러스터에는 $N$대의 컴퓨터가 있으며, 각각의 성능은 $a_i$라는 정수로 평가할 수 있다.

현지는 각각의 컴퓨터에 비용을 들여 업그레이드를 진행할 수 있다.

성능을 $d$만큼 향상시키는 데에 드는 비용은 $d^2$원이다.

업그레이드를 하지 않는 컴퓨터가 있어도 되지만, 한 컴퓨터에 두 번 이상 업그레이드를 수행할 수는 없다.

 

업그레이드를 위한 예산이 $B$원 책정되어 있다.

현지의 목표는 $B$원 이하의 총 비용으로 업그레이드를 수행하여, 성능이 가장 낮은 컴퓨터의 성능을 최대화하는 것이 목표이다.

이 최선의 최저성능을 계산하는 프로그램을 작성하시오.

 

<입력>

 

<출력>

첫째 줄에 예산을 효율적으로 사용했을 때, 성능이 가장 낮은 컴퓨터의 성능으로 가능한 최댓값을 출력하시오.

---

풀이

입력 범위를 보면 가장 낮은 컴퓨터의 성능의 최댓값은 $a_i$가 $10^9$이고, $B$가 $10^18$일 때 $2\times 10^9$이다.

따라서 $1$~$2 \times 10^9$까지 범위에서 이진탐색을 적용해보자.

 

설명에 비해 간단한 문제이다.

파이썬으로 작성하면 18줄만에 정답코드를 작성할 수 있다.

자료형에 대한 고민이 필요없기 때문이다.

n,b =map(int,input().split())
a = list(map(int,input().split()))

low, high = 1, 2*10**9
while low <= high:
    mid = (low+high+1)//2
    if test(mid):
        low = mid
    else:
        high = mid-1
print(low)

def test(x):
    cost = 0
    for i in range(n):
        if(a[i]<x):
            cost += (x-a[i])*(x-a[i])
    return cost <= b

 

다만 high 가 low +1 이면 mid 가 low 가 되어 무한루프가 돌 수 있기 때문에

mid = (low+high+1)//2 처럼 +1을 해줘야 한다.