[백준] 17245번 : 서버실

🔗 문제 링크

https://www.acmicpc.net/problem/17245

✍️ 문제 풀이

해당 문제는 이진 탐색 중에서 lowerBound를 이용했다. 작동하는 컴퓨터 개수가 처음으로 절반 이상을 넘는 시간을 구하면 되기 때문이다.

1) 각 칸들의 컴퓨터 개수를 저장하는 벡터 arr을 선언한다.

2) 각 칸들의 컴퓨터 개수를 입력 받아 arr에 삽입한다. 입력 받을 때 모든 수를 sum에 더해 전체 컴퓨터 개수를 저장한다.

3) sum을 절반으로 나누어 전체 컴퓨터 개수의 절반 이상이 몇 개인지 half에 저장한다.

• 이 때, 컴퓨터 개수가 홀수라면 절반 이상을 구하기 위해 반내림이 아니라 반올림 해주어야 하기 때문에 정수 2가 아닌 실수 2.0으로 나누고, round 함수로 묶어 반올림 처리해준다.

4) 이진 탐색을 위해서는 정렬해주어야 하기 때문에 arr을 sort로 오름차순 정렬해준다.

5) lowerBound() 함수를 실행해 처음으로 절반 이상을 넘게 되는 시간(== 층)을 반환한다.

• start = 0, end = 가장 컴퓨터 개수가 많은 칸의 컴퓨터 개수로 초기화 한다.
• 현재 냉기가 찬 층이 mid층이라고 가정할 때, mid층 이상 컴퓨터가 쌓여있는 칸은 mid만큼만 개수를 더해주고, mid층보다 적게 깔려있는 칸은 해당 칸의 컴퓨터 개수를 전부 더해준다.
  • 그 결과가 half보다 크거나 같다면 end를 mid의 자리로 옮겨준다.
  • half보다 작다면 start를 mid + 1의 자리로 옮겨준다.
• 위 과정을 반복하면서 start와 end를 옮기다가 end가 start보다 크지 않게 되는 순간(!(end > start))의 end 값을 반환해 출력한다.

🖥️ 풀이 코드

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

using namespace std;
vector<int> arr;
long long sum = 0;
long long half = 0;

int lowerBound(int n)		// 총합이 절반을 처음 넘는 층을 구해야 하므로 lowerBound로 처리
{
	int start = 0, end = arr[arr.size() - 1], mid = 0;
	long long tmpSum = 0;

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

		for (int i = 0; i < arr.size(); i++)	// 현재 층이 mid층 일 때
		{
			if (arr[i] >= mid)	
				tmpSum += mid;		// mid층 이상 컴퓨터 쌓여있는 칸은 mid 만큼 개수 더하기
			else
				tmpSum += arr[i];	// mid층보다 적게 깔려있는 칸은 해당 칸 총 개수 더하기
		}

		if (tmpSum >= half)			
			end = mid;
		else
			start = mid + 1;

		tmpSum = 0;
	}

	return end;
}

int main()
{
	int n;
	cin >> n;
	cin.ignore();

	for (int i = 0; i < n * n; i++)
	{
		int num;
		cin >> num;
		arr.push_back(num);
		sum += num;
	}
	half = round(sum / 2.0);

	sort(arr.begin(), arr.end());

	cout << lowerBound(n);
}