[BOJ] 히오스 프로게이머 16564 C++ 풀이

문제

히오스 프로게이머

접근방법

upper_bound(x.begin(), x.end(), Min) - x.begin(); 는 n개의 레벨중에서 가장 작은수 다음으로 큰 값의 인덱스를 반환하고 이는 가장 작은수의 개수와 같다.

즉 배열 x에 가장 작은 레벨이 총 minNum개 존재한다.

이때 주의해야 할 것이, 만약 upper_bound를 사용하여 키값을 탐색할때, 해당 키값이 배열에 존재하지 않으면 x.end(), 즉 값이 저장되지 않은 끝의 n을 반환하게 된다. 때문에 “Out of bound” 에러에 의한 런타임 에러를 주의해야 한다.

때문에 다음과 같은 예외 처리문을 넣어주었다.

if(minNum==n) nextNum = x[minNum-1];
else nextNum = x[minNum];

만약 최소값들에 minNum 만큼 k를 분배할때 최소값이 그보다 바로 큰값과 같아지게 된다면 최소값을 nextNum으로 갱신하고 위의 과정을 반복한다.

k를 minNum 만큼 각각의 최소값에 전부 분배해도 최소값이 nextNum보다 여전히 작다면 모든 k를 minNum개 만큼 나눠서 최소값에 더해주면 Min이 가능한 최소레벨 값이 된다.

구현

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

int main(void)
{
    ios::sync_with_stdio(false); cin.tie(0);
    int n, k, level;
    int Min, minNum;
    vector<int> x;

    cin>>n>>k;

    if(n==1)
    {
        cout<<n+k<<'\n';
        return 0;
    }

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

    sort(x.begin(), x.end());
    Min = x[0];
    
   minNum = upper_bound(x.begin(), x.end(), Min) - x.begin(); 

    while(1)
    {
        int nextNum;
        if(minNum==n) nextNum = x[minNum-1];
        else nextNum = x[minNum];

        if((Min + (k/minNum)) >= nextNum && minNum!=n)
        {
            k = k - (minNum * (nextNum - Min));
            Min = nextNum;
            minNum = upper_bound(x.begin(), x.end(), Min) - x.begin(); 
        }
        else
        {
            k/=minNum;
            Min += k;
            break;
        }
    }

    cout<<Min<<'\n';
    return 0;
}