[PS] 백준 #16564. 히오스 프로게이머

문제 정보

• 난이도: 실버 I
• 문제 주소: https://www.acmicpc.net/problem/16564
• 이 문제를 푼 이유: 그룹 연습 Div 2

 

문제

성권이는 Heroes of the Storm 프로게이머 지망생이다.

이 게임에는 총 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: 내 풀이

레벨들을 정렬한 후, T값은 가장 낮은 레벨에서 시작한다. 가장 낮은 레벨이 두번째 레벨만큼 올라오면 T는 두번째 레벨로 갱신해주고 k는 (charCount * 두 레벨의 차이)만큼 감소, charCount는 1 증가시킨다. 만약 k값이 두 레벨의 차이만큼 올리기에 충분하지 않을 경우 몫 계산해서 반복문을 종료한다. 

#include <bits/stdc++.h>
using namespace std;

int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	vector<int> levels;
	int n, k;
	cin >> n >> k;
	levels.push_back(0); // 0번째 값은 쓰레기값
	for (int i = 0; i < n; i++) {
		int a; cin >> a; levels.push_back(a);
	}

	// levels 오름차순 정렬
	sort(levels.begin(), levels.end());

	// T값은 가장 낮은 레벨에서 시작한다. 
    // 가장 낮은 레벨이 두번째 레벨만큼 올라오면 T는 두번째 레벨로 갱신
    // k는 (charCount * 두 레벨의 차이)만큼 감소하고, charCount 1 증가
    // 만약 k값이 두 레벨의 차이만큼 올리기에 충분하지 않을 경우 몫 계산해서 반복문 종료
	int T = levels[1];
	int charCount = 1;
	while (k > 0) {
		if (charCount < levels.size()) {
			if ((levels[charCount + 1] - levels[charCount]) * charCount <= k) {
				T = levels[charCount + 1];			
				k -= (levels[charCount + 1] - levels[charCount]) * charCount;
				charCount++;
			}
			else {
				T += k / charCount; break;
			}
		}
		else break;
	}

	cout << T;
}

 

풀이 2: 이분탐색

대회가 끝난 후 해설을 보니 원래는 이분 탐색을 이용한 풀이가 정석 방법인 것 같았다. 내가 푼 풀이가 이분 탐색을 사용한 풀이인지는 잘 이해가 안가서.. 다시 아래와 같이 풀어보았다. 나는 예전부터 이분 탐색 관련 문제들은 잘 눈치채지 못하는 경우가 많았어서 이 테마는 조금 더 연습이 필요할 것 같다. 

l과 r을 T값의 범위라고 생각하자. 이분탐색의 각 과정마다 l과 r의 중간인 mid 를 계산하고, mid보다 작은 레벨들과의 차이를 dt에 추가하자. dt가 k보다 크면 r을 mid-1로 옮겨서 범위를 좌측 반으로 줄인다. dt가 k와 같거나 작으면 answer에 mid를 대입하고, l을 mid+1로 옮겨서 범위를 우측 반으로 줄인다. 이 과정을 반복하다가 l > r이 되서 알고리즘이 종료된다. 그 때의 mid값이 최종 정답이다.

#include <bits/stdc++.h>
using namespace std;

int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	vector<int> levels;
	int n, k;
	cin >> n >> k;
	levels.push_back(0); // 0번째 값은 쓰레기값
	for (int i = 0; i < n; i++) {
		int a; cin >> a; levels.push_back(a);
	}

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

	long dt, l = 0, r = 1000000000, answer;
	while (l <= r) {
		long mid = (l + r) / 2;
		dt = 0;
		// mid 보다 작을때만 dt값 갱신
		for (int i = 1; i <= n; i++) {
			if (levels[i] < mid) dt  += mid - levels[i];
		}
		if (dt > k) {
			r = mid - 1;
		}
		else {
			answer = mid;
			l = mid + 1;
		}
	}

	cout << answer;
}