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

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

Softeer

풀이

업그레이드를 위한 비용 B가 책정되어 있을 때, B원 이하로 성능이 가장 낮은 컴퓨터의 성능을 최대화 하고 싶다. 이 때, 성능이 가장 낮은 컴퓨터의 성능으로 가능한 최대값을 찾아야 한다.

1. 제한 조건의 범위가 크기 때문에 이분탐색을 사용해서 문제를 풀었다.

2. 이때, 답(mid)은 성능이 가장 낮은 컴퓨터의 성능 최대값으로 가정하고, 성능이 10^9 인 컴퓨터 1대에 10^18의 비용을 들여서 업그레이드를 할 경우, 성능은 10^9 + 10^9 = 2*10^9 이므로 right = 2*10^9로 설정하고 알고리즘을 돌리면 된다.

3. Total <= B 가 되는 경우가 답으로 가능한 후보이기 때문에 answer를 업데이트 해준다.

리뷰

주의할 점은 비용을 계산하면서

if (total > B) break;

가 없을 경우 오답이 난다는 것이었다.

아마 모든 컴퓨터에 대해 sum을 하기 때문에 total 값이 ll 범위를 벗어나서 생기는 오답인 것 같다..

#include<iostream>
#include<vector>
#include <algorithm>

using namespace std;

#define ll unsigned long long int
int main(int argc, char** argv)
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	ll N, B, a, mid, answer;
	ll left = 1;
	ll right = 2000000000;
	vector<ll> comps; 
	cin >> N >> B;
	for (ll i = 0; i < N; i++) {
		cin >> a;
		comps.push_back(a);
	}
	sort(comps.begin(), comps.end());
	
	while (left <= right) {
		ll mid = (left + right)/2;
		ll total = 0;
		for (ll i = 0; i < N; i++) {
			if (comps[i] < mid) {
				total += (mid - comps[i]) * (mid - comps[i]);
				if (total > B) break;
			}
		}
		
		if (total == B) {
			answer = mid;
			break;
		}
		
		if (total > B) {
			right = mid - 1;
		}
		else {
			left = mid + 1;
			answer = mid;
		}
		
	}

	cout << answer << endl;
	return 0;
}