[소프티어] 슈퍼컴퓨터 클러스터 (Java)

문제

Softeer

 

 

알고리즘

이분 탐색, 파라메트릭 서치

 

 

풀이

이분 탐색을 진행하며 주어진 예산으로 만들 수 있는 성능의 최댓값을 출력한다.

 

이분 탐색

left는 하나의 컴퓨터도 업그레이드를 할 수 없는 경우 최솟값:  현재 a 중 최솟값, 

right는 주어진 예산을 이용하여 업그레이드할 수 있는 최댓값: 현재 a 중 최댓값 + B의 제곱근

 

코드에서는 조금 더 넓은 범위인 left: 0 , right: 1e9 + sqrt(B) 로 설정하였다.

left와 right의 평균값인 mid 에 대해 업그레이드가 가능하다면

그 이상의 값으로 업그레이드가 가능한지 확인하기 위해 left를 mid + 1 로 

그렇지 않다면 그 이하의 값으로 업그레이드가 가능한지 확인하기 위해 right를 mid - 1로 변경한다.

 

---

업그레이드 가능 확인

 

목표 성능보다 현재 성능이 낮은 컴퓨터들의 업그레이드 비용을 더하면서

그 비용이 예산 B보다 크다면 업그레이드가 불가능하므로 false를 반환하고

비용이 예산 B보다 작다면 업그레이드 가능하므로 true를 반환한다.

 

 

코드

import java.util.*;
import java.io.*;


public class Main
{
    static long B;
    static int[] arr;

    public static void main(String args[]) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        B = Long.parseLong(st.nextToken());

        arr = new int[N];

        st = new StringTokenizer(br.readLine(), " ");
        for(int i=0; i<N; i++)
            arr[i] = Integer.parseInt(st.nextToken());

        long left = 0;
        long right = (long) 1e9 + (long) Math.sqrt(B);

        while(left <= right) {
            long mid = (left + right) / 2;

            boolean s = check(mid);
            if(s) left = mid + 1;
            else right = mid - 1;
        }

        System.out.println(right);
    }

    public static boolean check(long target) {
        long cost = 0;

        for(int a: arr) {
            if(a < target) 
                cost += (target-a) * (target-a);

            if(cost > B) return false;
        }

        return true;
    }
}