[HSAT 4회 정기 코딩 인증평가 기출] 슈퍼컴퓨터 클러스터 (C++)

풀이

매개변수를 이용한 이분탐색 알고리즘 문제였다. 처음에 문제의 조건에서 B의 크기에 간과하여 시간이 꽤 소요되었는데, cost를 계산 후 매개변수의 차이의 합을 저장하던 중 자료형의 크기를 훨씬 넘어버리는 케이스를 생각하지 못하였다. overflow가 발생하면 더이상 차이의 합을 저장하지 않고 bool 타입 변수를 true로 조정 후 break문을 사용하여 넘어가는게 핵심이었던 문제이다.

 

#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
long long N,B,ans;
vector<long long> vec;
int main(int argc, char** argv)
{
	cin>>N>>B;
	vector<long long> vec(N);
	for(int i=0;i<N;i++){
		cin>>vec[i];
	}
	sort(vec.begin(),vec.end());
	long long l=1,r=2000000000;
	while(l <= r){
		long long mid = (l + r) / 2;
		unsigned long long sum = 0;
		bool overflow = false;
		for(int i=0;i<N;i++){
			if(mid-vec[i]>0){
				unsigned long long cost = pow(mid-vec[i],2);
				if(cost>B || sum>B-cost){
					overflow = true;
					break;
				}
				sum += cost;
			}
			else break;
		}
		if(overflow || sum > B){
			r = mid - 1;
		}
		else{
			ans = mid;
			l = mid + 1;
		}
    }
	cout<< ans;
	return 0;
}