백준 16564 히오스 프로게이머

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

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

using namespace std;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, k;

    cin >> n >> k;

    vector<int> x(n);

    for (int i = 0; i < n; i++) {
        cin >> x[i];
    }

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

    int l = x[0];
    int r = x[0] + k;
    int ans = 0;

    while (l <= r) {

        int mid = (l + r) / 2;
        long long need = 0;

        for (int i = 0; i < n; i++) {
            if (x[i] < mid) {
                need += mid - x[i];
            } else {
                break;
            }
        }

        if (need <= k) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }

    }

    cout << ans;

    return 0;
}

 

1. 문제

 n개의 캐릭터의 레벨과 올릴 수 있는 레벨 k가 주어진다. k를 n개의 캐릭터 중 적절히 분배하여 팀 목표레벨(n개 캐릭터의 레벨 중 최솟값)을 정하는 데, 이 값의 최대를 구하는 문제이다. 

2. 풀이

 

    int l = x[0];
    int r = x[0] + k;
    int ans = 0;

 

이분 탐색 문제이다. 팀 목표레벨의 최댓값을 구하는 문제이므로 이를 mid로 놓고 계산한다. 팀 목표레벨은 팀원 중 가장 낮은 레벨의 캐릭터에게 레벨을 분배하지 않는 게 최솟값이고, 가장 높은 레벨의 캐릭터에게 k를 모두 분배하는 게 최댓값이다. 이 범위에서 이분 탐색을 진행한다.

 while (l <= r) {

        int mid = (l + r) / 2;
        long long need = 0;

        for (int i = 0; i < n; i++) {
            if (x[i] < mid) {
                need += mid - x[i];
            } else {
                break;
            }
        }

        if (need <= k) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }

    }

 need는 mid가 팀 목표레벨일 때 분배해야 하는 레벨의 수이다. 각 캐릭터에 대하여 해당 캐릭터가 팀 목표 캐릭터보다 작을 경우 목표 레벨까지 올리고, 그 차이를 need에 더한다. 목표레벨보다 더 큰 경우에는 x를 정렬했으므로 반복문을 빠져나간다.

 need가 k 이하일 경우 목표 레벨의 최댓값을 구하는 문제이므로 k가 need와 같더라도 mid보다 높은 구간에 대하여 한번 더 연산을 진행한다. 반대의 경우에는 목표 레벨이 적어야 올려야 하는 레벨도 적으므로 mid보다 낮은 구간에 대하여 연산을 진행한다.

 위 연산을 통해 찾은 값 ans를 출력하면 정답을 구할 수 있다.