📝 문제
대규모 머신 러닝에서는 여러 컴퓨터를 하나의 클러스터로 묶어 계산을 수행하는 경우가 많다. 병렬 컴퓨팅 파워가 늘어나면 훨씬 더 거대한 데이터도 실용적으로 사용할 수 있게 된다. 클라우드 컴퓨팅을 이용하는 기업도 많지만, 개인정보와 보안, 네트워킹, 비용 등의 문제로 직접 클러스터를 구축하는 경우도 많다.
현지도 이러한 머신 러닝용 클러스터를 관리하는 역할을 맡고 있다. 클러스터의 성능은 컴퓨터의 수가 많아질 수록, 각각의 성능이 올라갈 수록 향상된다. 그런데 어느 날 협업 중인 몇몇 연구실에서 클러스터의 성능을 업그레이드해 달라는 요청을 보내 왔다. 이들은 특히 클러스터를 이루는 각각의 컴퓨터 중 성능이 가장 낮은 컴퓨터의 성능이 병목이 된다고 알려 왔다.
이 클러스터에는 N대의 컴퓨터가 있으며, 각각의 성능은 ai라는 정수로 평가할 수 있다. 현지는 각각의 컴퓨터에 비용을 들여 업그레이드를 진행할 수 있다. 성능을 d만큼 향상시키는 데에 드는 비용은 d2원이다. (단, d는 자연수이다.)
업그레이드를 하지 않는 컴퓨터가 있어도 되지만, 한 컴퓨터에 두 번 이상 업그레이드를 수행할 수는 없다.
업그레이드를 위한 예산이 B원 책정되어 있다. 현지의 목표는 B원 이하의 총 비용으로 업그레이드를 수행하여, 성능이 가장 낮은 컴퓨터의 성능을 최대화하는 것이 목표이다. 이 최선의 최저성능을 계산하는 프로그램을 작성하시오.
제약조건
1≤ N ≤ 105인 정수
1≤ ai ≤1010인 정수
1≤ B ≤1018인 정수
입력형식
첫째 줄에 컴퓨터의 수와 예산을 나타내는 정수 N과 B가 공백을 사이에 두고 주어진다. 둘째 줄에 각 컴퓨터의 성능을 나타내는 N개의 정수 a1, a2, ..., an이 공백을 사이에 두고 주어진다.
B의 범위가 매우 넓어, 사용하는 프로그래밍 언어에 따라 64비트 정수형을 사용해야 할 수 있음에 유의하시오.
출력형식
첫째 줄에 예산을 효율적으로 사용했을 때, 성능이 가장 낮은 컴퓨터의 성능으로 가능한 최댓값을 출력하시오.
입력예제1
4 10
5 5 6 1
출력예제1
4
네 번째 컴퓨터의 성능을 1에서 4로 업그레이드 하는 데 드는 비용은 32=9원이다. 이 경우, 가장 낮은 성능의 컴퓨터는 4의 성능을 가지게 되며, 가장 낮은 성능으로 가능한 최대값은 4가 됨을 알 수 있다.
입력예제2
10 10
5 3 9 8 4 3 1 8 6 3
출력예제2
3
일곱 번째 컴퓨터의 성능을 1에서 3으로 업그레이드 하는 데 드는 비용은 22=4원이다. 이 경우, 가장 낮은 성능의 컴퓨터는 3의 성능을 가지게 된다.
가장 낮은 성능이 4가 되기 위해서는 원래 3의 성능을 가지고 있었던 두 번째, 여섯 번째, 그리고 열 번째 컴퓨터를 향상시키는 데 드는 비용 12+12+12=3원과 일곱 번째 컴퓨터의 성능을 3이 아닌 4로 향상시키는 데 드는 비용 (4-1)2=9원, 총 12원이 들기 때문에 불가능하다.
입력예제3
10 10000000
10 2 2 9 6 1 8 3 1 9
출력예제3
1005
💡 Solution
입력이 커서 모든 경우의 수를 따져서 풀면 안되고 이진 탐색으로 접근해야 하는 문제.
- 성능이 가장 낮은 컴퓨터의 가능한 성능 범위는 컴퓨터 성능들의 최솟값 ~ 컴퓨터 성능들의 최댓값 + 예산 B의 제곱근
- 성능 범위를 이진 탐색으로 해서 가장 낮은 컴퓨터의 최대 성능을 찾자.
<예산 내에서 업그레이드 할 수 있는지 확인>
2-1. 기준 값 ( 가장 낮은 컴퓨터 성능이라고 가정하는) - 원래 컴퓨터 성능 > 0 이면 두개 뺀 값 만큼 성능을 올려줘야 함
2-2. 그리고 cost(성능 증가 시켰을 때 드는 비용)에 두개 뺀 값의 제곱을 더해 준다.
2-3. cost가 예산 보다 커지면 false(right를 mid -1) 아니면 true (left를 mid+1) true 일땐 answer에 가장 낮은 성능 값 업데이트
✔ 참고자료
🔑 code
import java.util.Arrays;
import java.util.Scanner;
public class 슈퍼컴퓨터클러스터 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 컴퓨터 수 1≤N≤10^5인 정수
long b = sc.nextLong(); // 예산 1≤B≤10^18인 정수
long[] computer = new long[n];
for(int i=0; i<n; i++){
computer[i] = sc.nextLong(); //컴퓨터 성능 ai 1≤N≤10^9인 정수
}
Arrays.sort(computer);
// 제일 성능이 낮은 컴퓨터의 성능 최소, 최대값
long min = computer[0];
long max = computer[n-1] + (long)Math.sqrt(b);
long answer = 0;
//이분 탐색으로 제일 낮은 성능 컴퓨터 찾기
while( min <= max){
long mid = (min + max)/2;
if(check(computer, mid, b)){ //예산을 더 키워도 된다
min = mid +1;
answer = mid;
}else{
max = mid -1 ;
}
}
System.out.println(answer);
}
private static boolean check(long[] computer, long mid, long b) {
long cost = 0;
for(int i=0; i < computer.length ; i++){
cost += mid - computer[i] > 0 ? Math.pow(mid-computer[i],2) : 0; // 성능 최소 값 - 지금 성능
if(cost > b) return false;
}
return true;
}
}
📚알고리즘 분류
이진 탐색
