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

문제 링크

16564번: 히오스 프로게이머

문제 요약

N개의 캐릭터에 대한 레벨이 주어진다. 팀의 목표 레벨을 캐릭터들의 레벨의 최솟값으로 정의한다. 캐릭터들의 레벨은 총 K만큼 올릴 수 있다. 이때 캐릭터들의 레벨을 올려서 가능해지는 최대 팀 목표 레벨을 구해야한다.

접근 방법

이분탐색 문제임을 보자마자 생각해낼 수 있었습니다.

1. low와 high를 정하고 (low+high)/2를 mid로 정합니다. 이때 mid는 팀의 목표 레벨입니다.
2. 이제 각 캐릭터들의 현재 레벨과 팀 목표 레벨을 비교하고, 팀 목표 레벨보다 캐릭터의 현재 레벨이 작은 경우, 그 차의 합을 구합니다.
3. 이 합이 K보다 큰 경우에는 high를 mid로, 작거나 같은 경우에는 low를 mid로 이동시킵니다.

과거에는 이분탐색 문제를 풀때 실수를 엄청 많이 했던 것 같은데 백준에서 이 글을 읽고 나서부터는 실수가 줄게 된거 같습니다.

코드

#include <bits/stdc++.h>
#define VPRT(x, type) copy(x.begin(), x.end(), ostream_iterator<type>(cout, " "))
#define ALL(x) x.begin(), x.end()
#define FASTIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'

using namespace std;

long long n, k;
vector<int> x;

bool check(int num)
{
	long long sum = 0;
	for (auto& i : x)
		if (i < num)
			sum += (num - i);

	if (sum > k)
		return false;
	return true;
}

int main(void)
{
	FASTIO;
	cin >> n >> k;

	for (int i = 0; i < n; i++)
	{
		int num;
		cin >> num;
		x.push_back(num);
	}

	int low = 1, high = 2e9, mid = 0;
	while (low + 1 < high)
	{
		mid = (low + high) / 2;

		if (check(mid))
			low = mid;
		else
			high = mid;
	}

	cout << low << endl;
	return 0;
}