[BOJ] 16564번_히오스 프로게이머_이분 탐색 (C++)

[문제]

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

히오스라는 게임에는 총 N개의 캐릭터가 있다. 그리고 현재 각 캐릭터의 레벨은 Xi이다. 성권이는 앞으로 게임이 끝날 때까지, 레벨을 최대 총합 K만큼 올릴 수 있다.

팀 목표레벨 T=min(Xi)(1<=i<=N)라고 정의하면, 게임이 끝날 때까지 성구너이가 달성할 수 있는 최대 팀 목표레벨 T를 구하는 문제이다.

예를 들어, N=3, X1=10, X2=20, X3=15이고 K=10일 때, X1을 7만큼 올리고 X3을 2만큼 올리면 최소 레벨 Xi는 17이 된다. 따라서 팀 목표레벨 T는 17이다. 이 경우처럼 레벨을 총합 K보다 적게 올릴 수도 있다.

[사용 알고리즘]

이분 탐색

[풀이 핵심]

• 이분 탐색을 돌때 1레벨부터 시작해서 K만큼 레벨업 할 수 있으므로,1부터 1+K의 최대값(1,000,000,000)까지 이분탐색을 돌아야한다. (start = 1, end = 1,000,000,001)
• sum 변수는 모든 캐릭터의 레벨을 mid까지 올릴 때, 필요한 레벨의 총합이므로 int의 최대값을 넘을 수 있다. 따라서 long long 타입으로 선언해줘야한다.

[코드]

//boj16564번_히오스 프로게이머_이분 탐색

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main() {
	int N, K;
	cin >> N >> K;

	vector<int> v;

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

		v.push_back(X);
	}

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

	int start = 1;
	int end = 1000000001;

	int result = 0;

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

		for (int i = 0; i < v.size(); i++) {
			if (v[i] < mid) {
				sum += mid - v[i];
			}
		}

		if (sum <= K) {
			start = mid + 1;
			result = mid;
		}
		else {
			end = mid - 1;
		}
	}

	cout << result;

	return 0;
}