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

문제)https://softeer.ai/practice/6252

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

 

풀이)

어떻게 보면 일반적인 이진탐색 문제인데, 문제 보고 떠올리기가 쉽지않았다. DP같기도 하고... 하지만 떠올리기만 하면 괜찮은 문제로 보인다. target을 컴퓨터들의 최소성능으로 잡고, mid값이 예산보다 작으면, target을 키워서 탐색. mid값이 예산보다 크면 , target값을 작게 잡고 탐색한다고 생각하고 풀었다. 

 

코드)

#include <bits/stdc++.h>
using namespace std;

#define ll long long

ll N, B;
vector <ll> v;
bool check(ll num) {
    ll sum = 0;
    for (int i = 0; i < v.size(); ++i) {
        if(v[i] >= num) break;
        sum += (num - v[i]) * (num - v[i]);
        if(sum > B)return false;
    }
    if(sum > B)return false;
    else return true;
}


int main(){
    cin >> N >> B;
    ll num;
    for (int i = 0; i < N; ++i) {
        cin >> num;
        v.push_back(num);
    }
    sort(v.begin(), v.end());
    int answer;
    ll st = v[0];
    ll ed = 2000000000;
    while(st <= ed){
        ll mid = (st + ed)/2;
        if(check(mid)) {
            st = mid + 1; //찾는 거뒤면
            answer = mid;
        }
        else ed = mid - 1; //찾는 거앞이면
    }

    cout << answer;

}