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

문제

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

16564번: 히오스 프로게이머

 

사용한 알고리즘

2022.02.02 - [PS/Algorithm] - [알고리즘 개념정리] 7. 이분탐색/분할정복

-> 매개변수 탐색

 

풀이 

팀 목표  레벨의 '최댓값'을 구하는 문제이므로 최적화 문제라고 할 수 있다.
결정 문제로 바꾸어 푸는 매개변수 탐색 기법을 사용해보자.

목표레벨 T는 최초 레벨들 중 최소값보다 작을 수 없고(레벨은 올라가기만 함),
가능한 T의 최댓값은 캐릭터가 하나일 때, Xi, K가 최대인 경우이다.

T의 range = [min(Xi), 2*10^9] = [1~20억] = [1~2^31] 
따라서 이분탐색을 이용하면 31번의 반복을 통해 구간길이를 1로 만들 수 있다.

 

목표레벨 T가 가능한 최대 팀 목표레벨이라고 한다면,
T-1, T-2 ... 도 목표레벨이 가능하다. 
하지만 T+1, T+2 ... 는 불가능하다.

그 경계점을 이분탐색으로 찾아주면 된다!

즉, T의 범위인 min(Xi)~min(Xi)+k 내에서 이분탐색하면서
mid=T'에서 가능한지 체크하고 가능한 가장 큰 T'값을 출력하면 된다.
이때 가능하다는 뜻은, (Xi<T일때 T-Xi 차이들의 합) <= k 인 경우를 말한다.

 

시간 복잡도

mid값이 가능한지 확인하는데 O(N),
이분탐색하는데 O(logL) 이므로 총 O(NlogN)이다.

이 문제에서의 탐색 범위는 [1~2^31] 이므로
logN = 31 이다.

따라서 총 시간복잡도는 O(31N) = O(N) 이다.

 

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n,k;
vector<int> level; //Xi들을 담는 곳

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin>>n>>k;
    for(int i=0; i<n; i++){int x; cin>>x; level.push_back(x);}
    sort(level.begin(), level.end());

    // r은 최대 20억이라 int해도 되는데, need는 최대 nk라서 롱롱 해야됨
    int l=level[0], r=level[0]+k, mid=0, ans=0;
    long long need =0;
    while(l<=r){
        mid = (l+r)/2, need=0;

        for(int i=0; i<n; i++){
            if(level[i]<mid) need+=mid-level[i];
            else break; //오름차순 정렬되어있기 때문
        }
        if(need>k) r=mid-1;
        else{
            ans=mid;
            l=mid+1;
        }
    }
    cout<<ans;
    return 0;
}