[Softeer] 슈퍼컴퓨터 클러스터 with C++ (HSAT 4회 기출)

https://softeer.ai/practice/6252

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

언어: C++, 시간: 36ms

 

접근방법

N이 크기 때문에 시간 최적화가 필요하다. 

난 이진탐색의 업그레이드 버전인 Parametric search(매개변수 탐색)을 이용했다.

 

1. 문제에서 가능한 정답의 범위(최선의 최소 컴퓨팅 성능): 

 성능이 가장 낮은 컴퓨터 ~ 성능이 가장 높은 컴퓨터 + B의 루트 값

 

2. 최선의 최소 컴퓨팅 성능이 num일 때 예산 안에서 업그레이드가 가능한지 판별하는 함수 isPossible을 만들어준다!

이후 가능한 정답 범위에서 이진탐색을 한다! → isPossible이 true면 start = mid + 1, false면 end = mid -1로 업데이트

 

이걸 하기 위해선 먼저 컴퓨터들을 오름차순으로 정렬해주어야 한다.

 

 

주의사항

문제에서 예산 B가 int 범위를 넘어가므로 long long이 필요하다!🫥

 

 

최종코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

int N, temp;
long long B, minNum, maxNum;
vector <int> computers;

// 최소 컴퓨터 성능을 num으로 만들때 예산 안에서 가능한지를 판별한다. 
bool isPossible(long long num) {
    long long sum = 0;

    for (int i = 0; i < N; i++) {

        if (computers[i] >= num)
            break;

        long long gap = (num - computers[i]);
        sum += (gap * gap);
        
        if (sum > B)
            return false;
    }
    
    return true;
}

// start ~ end 중 최소 컴퓨터 성능의 최댓값을 반환하는 함수
long long ps(long long start, long long end) {

    long long answer = 0;
    
    while (start <= end) {
        long long mid = (start + end) / 2;

        if (isPossible(mid)) {
            answer = mid;
            start = mid + 1;
        }

        else
            end = mid - 1;
    }

    return answer;
}


int main() {
    //freopen("sample_input.txt", "r", stdin);

    cin >> N >> B;
    for (int i = 0; i < N; i++) {
        cin >> temp;
        computers.push_back(temp);
    }
    sort(computers.begin(), computers.end());    // 오름차순 정렬
    minNum = computers[0];
    maxNum = computers[N - 1];

    cout << ps(minNum, (int)(sqrt(B)));		// parametric search로 구한 것 출력하기

    return 0;
}