[소프티어] 슈퍼컴퓨터 클러스터 / C++ 해설

더 많은 문제풀이는 아래 Github 주소에서 확인하실 수 있습니다.

https://github.com/Dongha-k/softeer-code

GitHub - Dongha-k/softeer-code: softeer 문제 풀이입니다.

 

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

Softeer

 

소프티어 공식해설: https://softeer.ai/community/view.do?idx=731&cd=edu&pageNo=1

Softeer

 

 

알고리즘 분류: 이분탐색

주의할 것: 데이터의 범위

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>

using namespace std;
typedef unsigned long long ll;

int main(int argc, char** argv)
{
	int n;
	char str[20];
	cin >> n;
	cin >> str;
	
	ll b = atoll(str);
	
	vector<ll> a(n);
	for(int i = 0 ; i < n ; i ++){
		cin >> a[i];
	}
	sort(a.begin(), a.end());
	
	ll first = a.front();
	ll last = a.back() + (ll) pow(b, 0.5);
	ll answer = 0;
	
	while(first <= last){
	
		ll mid = (first + last) / 2; // mid : 최소 성능
		ll bal = 0;
		
		bool inBound = true;
		for(int i = 0 ; i < n ; i ++){
			if(a[i] >= mid) break;
			else if(bal + (mid - a[i]) * (mid - a[i]) > b){
				inBound = false;
				break;
			}
			else bal += (mid - a[i]) * (mid - a[i]);
		}

		if(inBound){
			first = mid + 1;
			answer = mid;
		}
		else last = mid - 1;
	}
	
	cout << answer;

	return 0;
}

 

설명

 

정해진 예산으로 가능한 슈퍼컴퓨터들 중 최소 성능의 컴퓨터의 성능이 가장 높아지도록 컴퓨터의 성능을 선택해야하는 문제이다. 이분탐색을 통해서 first와 last 사이에서 주어진 조건을 만족하면서 가장 최대의 값을 찾도록 선택하였다.

 

0. 그렇기에 컴퓨터의 최소 성능을 mid로 잡았다.

 

 

1. 그리고 first는 입력 받은 컴퓨터 중 가장 낮은 성능 값을 대입해주었다. (최소한에 비용을 지불하지 않는 경우 최소 성능을 가진 컴퓨터의 성능이 최소 성능이 될 것이기 때문에)

 

 

2. last는 가장 크게 최소 성능을 가지는 경우는 언제일까? 만약 성능이 4인 컴퓨터 하나만 입력으로 주어지고 Balance 가 9이면 그때 최소 컴퓨터 성능은 4 + 3 = 7일 것이다. 그렇기 때문에 입력 컴퓨터 중 최대 성능을 가지는 컴퓨터의 성능 + sqrt(B)로 설정하였다.

 

 

3. mid롤 움직이면서 그 mid(최소성능)이 정해진 예상으로 업그레이드가 모두 가능한지 확인하고 모두 가능하다고 하면 mid(최소성능)을 높여보려고 시도한다. 즉, first = mid + 1를 해보며 정해진 예산을 만족하는 최대의 mid값을 찾는다.

 

 

4. inBound라는 bool type 변수는 최소성능이 mid로 구성이 가능한지 가능하다면 true / 가능하지 않다면 false를 가진다. for 문에서는 최소 성능보다 낮은 성능을 가진 컴퓨터만을 대상으로 (mid - a[i]) ^ 2만큼의 비용을 누적하면서 중간에 정해진 예산을 벗어나니 inBound를 false로 대입하고 반복문을 벗어난다. for문을 돌던 중 mid 보다 큰 a[i]가 나왔을 경우 이분탐색을 하기전에 성능을 오름차순으로 정렬했기에 그 이후부턴 컴퓨터의 성능이 무조건 mid보다 크다는 것이 보장된다. 그렇기에 이 경우에도 벗어나도 된다.

 

 

5. for문을 나왔을 경우 inBound가 정해지며 true이면 (예산으로 구매가 가능한 경우라면) first = mid + 1로 더 높은 값을 탐색해보며 예산이 벗어나면 last = mid - 1로 최소 성능을 낮춰보며 주어진 예산안에 들어오는 최소 성능(mid)를 찾는다.

 

 

주의할 점: 데이터의 범위

 

주어진 예산(B)이 10^18까지 입력으로 들어올 수 있다고 조건을 주었다.. int의 경우 약 -21억 ~ 21억까지 데이터를 표현할 수 있기 때문에 히든 케이스에서는 이 큰 값을 입력조차 못받아서 틀렸습니다라고 계속 나올 것 같다. 그렇기에 String으로 입력으로 예산을 받고 stoll으로 문자열을 long long 타입의 데이터 타입으로 변환하고 long long 변수에 저장하자!