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

문제 링크

성능 요약

메모리: 53.11 MB, 시간: 579 ms

문제 설명

대규모 머신 러닝에서는 여러 컴퓨터를 하나의 클러스터로 묶어 계산을 수행하는 경우가 많다. 병렬 컴퓨팅 파워가 늘어나면 훨씬 더 거대한 데이터도 실용적으로 사용할 수 있게 된다. 클라우드 컴퓨팅을 이용하는 기업도 많지만, 개인정보와 보안, 네트워킹, 비용 등의 문제로 직접 클러스터를 구축하는 경우도 많다.

현지도 이러한 머신 러닝용 클러스터를 관리하는 역할을 맡고 있다. 클러스터의 성능은 컴퓨터의 수가 많아질 수록, 각각의 성능이 올라갈 수록 향상된다. 그런데 어느 날 협업 중인 몇몇 연구실에서 클러스터의 성능을 업그레이드해 달라는 요청을 보내 왔다. 이들은 특히 클러스터를 이루는 각각의 컴퓨터 중 성능이 가장 낮은 컴퓨터의 성능이 병목이 된다고 알려 왔다.

이 클러스터에는 N대의 컴퓨터가 있으며, 각각의 성능은 ai라는 정수로 평가할 수 있다. 현지는 각각의 컴퓨터에 비용을 들여 업그레이드를 진행할 수 있다. 성능을 d만큼 향상시키는 데에 드는 비용은 d2원이다. (단, d는 자연수이다.)

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

업그레이드를 위한 예산이 B원 책정되어 있다. 현지의 목표는 B원 이하의 총 비용으로 업그레이드를 수행하여, 성능이 가장 낮은 컴퓨터의 성능을 최대화하는 것이 목표이다. 이 최선의 최저성능을 계산하는 프로그램을 작성하시오.

---

제약조건

1≤ N ≤ 105인 정수

1≤ ai ≤1010인 정수

1≤ B ≤1018인 정수

---

입력형식

첫째 줄에 컴퓨터의 수와 예산을 나타내는 정수 N과 B가 공백을 사이에 두고 주어진다. 둘째 줄에 각 컴퓨터의 성능을 나타내는 N개의 정수 a1, a2, ..., an이 공백을 사이에 두고 주어진다.

B의 범위가 매우 넓어, 사용하는 프로그래밍 언어에 따라 64비트 정수형을 사용해야 할 수 있음에 유의하시오.

출력형식

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

---

문제 풀이

• 시간초과 날정도로 큰 숫자라서 무작정 탐색하면 안된다는 건 알았지만
• 생각이 안나서 해설 찾아보니까 이분탐색 사용하면 된다 라고 해서 이분탐색 사용
  문제 해설
• 소프티어 문제들은 개념, 자료구조 사용만 잘하면 잘 풀리는 문제들인 것 같다
  • 소프티어 문제들로 개념을 더 익히면 좋을 듯

Solution

import java.util.Arrays;
import java.util.Scanner;

public class C1204_슈퍼컴퓨터클러스터 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long b = sc.nextLong();

        int[] computers = new int[n];
        for (int i = 0; i < n; i++) {
            computers[i] = sc.nextInt();

        }

        Arrays.sort(computers); // 오륾차순 정렬
        long left = computers[0]; // 최소값으로 초기화
        long right = computers[n - 1] + (long) Math.sqrt(b); // 최대값 + B원으로 최대 업그레이 할 수 있는 성능

        long answer = 0;
        while (left <= right) {
            long mid = (left + right) / 2;
            if (upgrade(computers, b, mid)) {
                left = mid + 1;
                answer = mid; // upgrade가 true이므로 mid까지는 업그레이 가능
            } else {
                right = mid - 1; // mid 값 만들 비용이 안됨
            }
        }

        System.out.println(answer);
    }

    public static boolean upgrade(int[] arr, long b, long min) {
        long cost = 0; // min을 만들 비용 계산
        for (int com : arr) {
            if (com < min) { // 최소가 되야할 값보다 작은 수는 업그레이드 비용 계산해줌
                cost += (min - com) * (min - com);
                if (cost > b) return false;
            }
        }
        return true;
    }


}