소프티어 - 슈퍼컴퓨터 클러스터

문제

https://softeer.ai/practice/6252

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

 

 

제약 조건

 

 

시간: 5초

메모리: 1024MB

 

 

입력으로 들어오는 수의 범위가 매우 커서 완전 탐색이 어렵기 때문에 이분 탐색으로 문제를 접근함.

 

 

start = 1 (모든 컴퓨터의 성능이 1 이상)

end = 2 * 10^9를 넣어 이분탐색을 진행한다. (모든 컴퓨터의 성능이 2*10^9 이상)

 

2 * 10^9인 이유

1대의 컴퓨터의 성능이 10^9이고, 예산이 10^18이 들어오면 성능을 10^9만큼 올릴 수 있다.

기존의 성능 10^9 + 올린 성능 10^9 = 2 * 10 ^ 9

 

canUpgrade(mid)를 통해 현재 예산으로 모든 컴퓨터의 성능이 mid 이상이 될 수 있는 지 확인한다.

static void binarySearch(long start, long end) {
    if(start>end)return;

    long mid = (start + end) / 2;

    if(canUpgrade(mid)) {
        if(maxPower < mid) {
            maxPower = mid;
        }
        binarySearch(mid+1, end);
    }
    else {
        binarySearch(start,mid - 1);
    }
}

static boolean canUpgrade(long wantMinPower) {
    BigInteger sum = BigInteger.valueOf(0);
    for (int i = 0; i < N; i++) {
        if (power[i] >= wantMinPower) {
            continue;
        } else {
            BigInteger tmp = BigInteger.valueOf(wantMinPower - power[i]);
            tmp = tmp.multiply(tmp);
            sum = sum.add(tmp);
        }
    }

    if (money.compareTo(sum) >= 0)
        return true;
    else
        return false;
}

 

전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

	static int N;
	static BigInteger money;
	static int[] power;
	static long maxPower = 0;

	public static void main(String[] args) throws Exception {

		init();
		binarySearch(1, Long.MAX_VALUE-1);
		System.out.println(maxPower);
	}

	static void binarySearch(long start, long end) {
		if(start>end)return;
		
		long mid = (start + end) / 2;
		
		if(canUpgrade(mid)) {
			if(maxPower < mid) {
				maxPower = mid;
			}
			binarySearch(mid+1, end);
		}
		else {
			binarySearch(start,mid - 1);
		}
	}

	static boolean canUpgrade(long wantMinPower) {
		BigInteger sum = BigInteger.valueOf(0);
		for (int i = 0; i < N; i++) {
			if (power[i] >= wantMinPower) {
				continue;
			} else {
				BigInteger tmp = BigInteger.valueOf(wantMinPower - power[i]);
				tmp = tmp.multiply(tmp);
				sum = sum.add(tmp);
			}
		}

		if (money.compareTo(sum) >= 0)
			return true;
		else
			return false;
	}

	static void init() throws Exception {
		StringTokenizer st = new StringTokenizer(in.readLine());
		N = Integer.parseInt(st.nextToken());
		money = new BigInteger(st.nextToken());
		power = new int[N];
		st = new StringTokenizer(in.readLine());
		for (int i = 0; i < N; i++) {
			power[i] = Integer.parseInt(st.nextToken());
		}
	}

}