[백준 16564번] 히오스 프로게이머 (C++)

문제링크 : https://www.acmicpc.net/problem/16564

16564번: 히오스 프로게이머

 

#include <bits/stdc++.h> 
using namespace std;
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);

long long n, k, sum, result = 0;
long long arr[1000001];

void binary_search(int l, int h)
{
	while (l <= h)
	{
		sum = 0;
		long long m = (l + h) / 2;  //중앙값 (목표레벨)
		for (int i = 0; i < n; i++)
		{
			if (m > arr[i])
			{
				sum += (m - arr[i]);  //중앙값과 각 값들의 차이의 합
			}
		}
		if (sum <= k)  //그 합이 레벨총합보다 같거나 작다면
		{
			l = m + 1;
			result = m;
		}
		else            //그 합이 레벨총합보다 크다면
		{
			h = m - 1;
		}
	}
}

int main()
{
	fastio;
	cin >> n >> k;
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
	}

	sort(arr, arr + n);

	binary_search(arr[0], arr[0] + k);  //정렬된 처음값, 처음값 + 레벨총합(k)

	cout << result;
	return 0;
}

 

먼저 입력받은 배열을 정렬을 시켜준 후,

정렬된 첫 값과 첫 값에 레벨총합을 더한 값을 low와 high로 두고 탐색을 시작한다.

(처음값 + 레벨총합 -> 나올 수 있는 최대값)

 

처음에 중앙값을 생성하고, 해당 중앙값과 배열의 각 값들의 차이의 합을 구해준다.

여기서 레벨 총합이 10이므로 위의 합이 10이하인 것은 괜찮지만 10을 넘어서면 안된다는 것을 알 수 있다.

 

위에서 구한 합을 바탕으로 합이 10이하 일때는 나올 수 있는 답이므로 result에 해당 중앙값을 저장한다.

하지만 조건에 맞는 답이 더 나올 수 있으므로 바로 break를 하지 않고 탐색을 이어간다.

 

합이 레벨총합보다 작을 때는 low에 m + 1, 클 때는 high에 m - 1을 대입하다가 low와 high가 같아지면 더 이상 탐색이 불가능하므로 종료한다.