[sof] 소프티어 <인증평가 4차 기출> 슈퍼컴퓨터 클러스터 (Java) - 이분탐색

[문제]

https://softeer.ai/practice/info.do?idx=1&eid=1204&sw_prbl_sbms_sn=171598 

Softeer

 

[풀이]

이분 탐색으로 풀 수 있다.

low값을 컴퓨터의 최저 성능인 capacity[0]로, high값은 컴퓨터의 최고 성능이 될 수 있는 현재의 최고 성능 값 + 최대로 업그레이드 가능한 점수 값으로 해준다.

최대 비용 B는 10^18 이고, d점을 올리는데 d^2 비용이 사용되므로 최대로 올릴 수 있는 점수는 Math.sqrt(B)이다. 

 

mid보다 낮은 컴퓨터 성능들을  B 비용 이내로 모두 mid 성능으로 올릴 수 있다면 low를 mid+1로 하여 mid 값을 높인다. 반대로 B 비용 이내에 mid 성능으로 올리는 것이 불가능하다면 high = mid-1로 하여 mid 값을 낮춘다.

 

주의해야 할 점은 calculate  함수 중간에 total이 B를 넘어설 경우 바로 false를 반환해줘야 한다. 다 계산한 다음 마지막에만 비교해서 true, false를 반환해주려 하는 경우 서브태스크를 통과하지 못하는데, total이 long의 범위를 벗어나 오버플로우가 발생하기 때문에 비교가 잘못되는 것 같다. 범위가 매우 크기 때문에 경계값에서 오류가 발생하지 않도록 주의해야 한다..

주어진 데이터의 범위가 매우 큰 경우 대부분 이분탐색 문제인 것 같다. 이분탐색 문제의 경우 오버플로우가 발생하지 않도록 알맞은 자료형을 사용할 수 있게 주의하자. 

 

[코드]

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        int N = Integer.parseInt(str[0]);
        long B = Long.parseLong(str[1]);

        str = br.readLine().split(" ");
        int[] capacity = new int[N];
        for (int i = 0; i < N; i++) {
            capacity[i] = Integer.parseInt(str[i]);
        }
        Arrays.sort(capacity);

        long low = capacity[0];
        long high = capacity[N - 1] + (long)Math.sqrt(B);
        long answer = 0;
        while (low <= high) {
            long mid = (low + high) / 2;

            if (calculate(mid, capacity, B)) {
                low = mid + 1;
                answer = mid;
            } else {
                high = mid - 1;
            }
        }
        System.out.println(answer);
    }

    public static boolean calculate(long mid, int[] capacity, long B) {
        long total = 0;
        for (int c : capacity) {
            if (c >= mid) break;

            total += (mid - c) * (mid - c);
            
            if (total > B) return false;
        }
        if(total > B) return false;
        else return true;
    }
}