[C++][백준] 17254 서버실

이 문제는 이분탐색을 이용하면 쉽게 풀리는 문제이다.

 

문제

서버실은 여러 대의 서버 컴퓨터들을 안정적으로 운영할 수 있는 환경을 유지하기 위해 설치된 공간을 말한다.
이 회사의 서버실은 N×N 칸으로 구분되어 있고, 각 칸마다 서버 랙이 있어 컴퓨터를 여러 대 쌓을 수 있다. 서버가 과열되지 않도록 서버실에는 언제나 냉방기가 작동하고 있다. 그런데 회사가 경제적으로 어려움에 처한 나머지, 서버실의 운영 비용을 줄이기 위해 서버실 내의 컴퓨터 중 절반만 정상적으로 관리하기로 하였다.
냉방기에서 나온 차가운 공기는 서버실의 아래쪽부터 서서히 차오른다. 1분마다 컴퓨터 한 대의 높이만큼 방을 채운다. 이 회사의 서버 컴퓨터는 환경에 매우 민감하여 차가운 공기를 받아야만 동작하고 그렇지 못하면 장애를 일으킨다.
서버실의 컴퓨터 중 절반 이상이 켜지려면 몇 분이 필요할까?

 

입력

정수 N이 주어진다. (1 ≤ N ≤ 1000)
N×N개의 각 칸에 컴퓨터가 몇 대 쌓여있는지가 입력된다. 한 칸에는 최대 10,000,000대까지 쌓여있을 수 있다.

 

출력

몇 분이 지나야 전체 컴퓨터의 절반 이상이 장애를 일으키지 않고 동작할 수 있는지 출력한다.

 

 

어떻게 풀어야 할까?

처음에는 N줄에 컴퓨터 수가 주어지는 줄 알고 부분합으로 풀어보려고 했지만, 문제를 잘못 이해했다는 것을 깨달았다.

그래서 N*N번 입력을 받고 적은 순서대로 정렬한 다음, 이진탐색을 돌렸다.

전체의 50%가 넘어가는 시점을 구하면 되기 때문에 NNNNYYYY경우 에서 N과 Y가 바뀌는 경우를 찾아내면 된다.

 

코드를 살펴보자

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<ll> arr;
    ll N,x,total=0,half=0,num=0;
    cin >> N;
    for(int i=0; i<N*N; i++){
        cin >> x;
        arr.push_back(x);
        total += x;
    }
    half = round(total*0.5);
    sort(arr.begin(),arr.end());
    ll start = 0, end = arr.back();
    while(start < end)
    {
        ll mid=(start+end)/2;
        num=0;
        for(ll i=0; i<arr.size(); i++)
        {
            if(arr[i] >= mid) num+=mid;
            else num += arr[i];
        }
        if(num >= half) end = mid;
        else start = mid+1;
    }
    cout <<  end;
    return 0;
}

 

• start는 가장 아래의 높이, end는 가장 높은 높이를 나타내줄 것이다.
• half는 전체 컴퓨터의 50%를 저장하는 변수이다. 여기서 중요한 것은 전체/2가 아니라 전체/2.0으로 해서 실수형으로 계산하고 반올림해주어야 한다.
• 이제 이분탐색을 진행해서 50%가 넘어가는 최소 값을 찾아내고 그 값을 반환하면 문제가 풀릴 것이다.