[소프티어] 슈퍼컴퓨터 클러스터 자바 풀이 이진탐색 시간초과 해결 (HSAT 4회 정기 코딩 인증평가 기출)

[소프티어] 슈퍼컴퓨터 클러스터 자바 풀이 이진탐색 시간초과 해결 (HSAT 4회 정기 코딩 인증평가 기출)

https://softeer.ai/practice/6252

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

 

 

 

 

 

 

 

언어별 시간/메모리

언어시간메모리

JavaScript	5초	1024MB
C	3초	1024MB
C++	3초	1024MB
Java	5초	1024MB
Python	5초	1024MB

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

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

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

 

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

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

제약조건

1≤N≤105인 정수

1≤ai≤109인 정수

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

 

 

 

 

 

 

핵심설명

입력은 롱으로

long b = Long.parseLong(st.nextToken());

 

루트(제곱근) 구하는 함수 이용해서, B원으로 업그레이드 가능한 최대 성능 설정하기

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

 

그놈의 이진탐색

while(left <= right){
    long mid = (left + right) / 2;
    // System.out.println("L M R : " + left+ " " + mid + " " + right);

    long cost = 0;
    boolean upgradeYn = true;

    // 대충 중간쯤 숫자 정해서
    // 해당 숫자를 기준으로 버전 업그레이드 해보자~
    for(int i : arr){
        if(i < mid){    // 업그레이드 기준 버전보다 작으면
            cost += ((mid-i)*(mid-i));  // 업그레이드해주고
            if(cost > b){
                upgradeYn = false;  // 해당버전까지 업그레이드 불가능
                break;
            }
        }
    }

    if(upgradeYn){  // 업그레이드 가능했다면, 비용이 남는거고, 더 높은 버전을 찾기위해, 반 짤라서 우측영역을 체크해보자
        left = mid+1;
        dap = mid; // mid까지는 업그레이드가 가능했음
    }else{          // 업그레이드 불가능했다면, 비용 부족하니, 낮은 버전을 찾기위해, 반 짤라서 좌측영역을 체크해보자
        right = mid-1;
    }
}

 

 

 

 

 

 

 

 

전체코드

import java.io.*;
import java.sql.SQLOutput;
import java.util.*;

public class Main {

    public static long dap = 0;

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        long b = Long.parseLong(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int arr[] = new int[n];
        for(int i=0; i<n; i++){
            int a = Integer.parseInt(st.nextToken());
            arr[i] = a;
        }
        // Arrays.sort(arr, Collections.reverseOrder());
        Arrays.sort(arr);
//        for(int i=0; i<n; i++){
//            System.out.print(arr[i] + " ");
//        }
//        System.out.println();

        // 이진탐색 시작
        long left = arr[0]; // 최소값으로 초기화
        long right = arr[n - 1] + (long)Math.sqrt(b); // 최대값 + B원으로 업그레이 할 수 있는 최대 성능
        while(left <= right){
            long mid = (left + right) / 2;
            // System.out.println("L M R : " + left+ " " + mid + " " + right);

            long cost = 0;
            boolean upgradeYn = true;

            // 대충 중간쯤 숫자 정해서
            // 해당 숫자를 기준으로 버전 업그레이드 해보자~
            for(int i : arr){
                if(i < mid){    // 업그레이드 기준 버전보다 작으면
                    cost += ((mid-i)*(mid-i));  // 업그레이드해주고
                    if(cost > b){
                        upgradeYn = false;  // 해당버전까지 업그레이드 불가능
                        break;
                    }
                }
            }

            if(upgradeYn){  // 업그레이드 가능했다면, 비용이 남는거고, 더 높은 버전을 찾기위해, 반 짤라서 우측영역을 체크해보자
                left = mid+1;
                dap = mid; // mid까지는 업그레이드가 가능했음
            }else{          // 업그레이드 불가능했다면, 비용 부족하니, 낮은 버전을 찾기위해, 반 짤라서 좌측영역을 체크해보자
                right = mid-1;
            }
        }

        bw.write(String.valueOf(dap) + "\n");
        bw.flush();
        bw.close();
        return;
    }

}