소프티어 [인증평가(4차) 기출] 슈퍼컴퓨터 클러스터

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

처음 이 문제를 보고 어느 컴퓨터를 최소로 해야하는지 판단이 안되었고 따라서 모든 경우의 수를 따져보아야 생각했고, 제약 사항을 보니

10^5(N) x 10^9(ai) = 10^14 이므로 완전탐색으로는 시간초과가 날 것이 틀림없어서 바로 이분탐색을 떠올렸습니다.

이분탐색과 파라메트릭 서치를 이용해서 문제를 해결하였습니다.

이분탐색

• left : 주어진 배열의 최솟값으로 초기화
• right : 주어진 배열의 최댓값 + 최대 업그레이드 가능 점수
• 가능한 값을 찾아도 최대값을 찾아야 하므로 탐색 계속 진행

		//a는 입력받은 배열(컴퓨터)
		Arrays.sort(a); //오름차순 정렬
		long left = a[0]; //최솟값으로 초기화
        long right = a[N - 1] + (long)Math.sqrt(B); 
        			//최댓값   + B원으로 최대 업그레이드 점수
       	long answer = 0;
        while (left <= right) {
            long mid = (left + right) / 2;

            if (파라메트릭 조건 == 참) {
                left = mid + 1;
                answer = mid;
            } else {
                right = mid - 1;
            }
        }

파라메트릭 서치

• min값을 배열의 최소값으로 만들 때 cost를 계산
  - a 배열을 돌면서 min보다 작은 원소들이 있다면 (min-i) * (min-i)의 합을 구함 == cost
• cost > B원 보다 크다면 해당 최소값을 만들 수 없음 --> return false;
• cost <= B원 --> return true;

public static boolean calculate(long min, int[] a, long B) {
        long cost = 0;
        for (int i : a) {
            if (i < min) {
                cost += (min - i) * (min - i);
                if (cost > B) return false;
            }
        }
        return true;
    }

전체코드

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

public class Softeer_cluster {
    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[] a = new int[N];
        for (int i = 0; i < N; i++) {
            a[i] = Integer.parseInt(str[i]);
        }
        Arrays.sort(a);
        long left = a[0];
        long right = a[N - 1] + (long)Math.sqrt(B);
        long answer = 0;
        while (left <= right) {
            long mid = (left + right) / 2;

            if (calculate(mid, a, B)) {
                left = mid + 1;
                answer = mid;
            } else {
                right = mid - 1;
            }
        }
        System.out.println(answer);
    }
    public static boolean calculate(long min, int[] a, long B) {
        long cost = 0;
        for (int i : a) {
            if (i < min) {
                cost += (min - i) * (min - i);
                if (cost > B) return false;
            }
        }
        return true;
    }
}

후기

• 제약조건을 보고 이분탐색을 빠르게 생각해냈는데, 데이터를 입력받을 때 int가 오버플러우 날 것을 생각을 못해서 헤멧다는게... 아이러니함..