문제

문제 링크

어떻게 접근할 것인가?

  • 이분탐색으로 접근하라고 되어있지만 이분탐색보다 직접 수학적으로 접근하는 것이 더 나을 것 같았다.
  • 앞서 풀었던 프로그래머스의 예산배정과 같은 식으로 접근했다.

프로그래머스 예산 풀이

코드

#include <string>
#include <algorithm>
#include <vector>
#include <cstdio>

using namespace std;


int main(){
    long long N, M, tree;
    vector<int> v;
    scanf("%lld %lld", &N, &M);
    for(int i = 0; i < N; i++){
        scanf("%lld", &tree);
        v.push_back(tree);
    }
    sort(v.begin(), v.end(), greater<int>());
    
    long long answer = 0;
    long long x = 0 ;
    for(int i =1; i < v.size(); i++){
        x += (v[i-1] - v[i]) * i;
        if(M == x){
            answer = v[i];
            break;
        }  
        if(M > x)continue;
        else{
            answer = v[i] + (x - M) / i;
            break;
        }
    }

    if(answer == 0){
        int p = (M - x) / N;
        if((M-x) % N != 0) p ++;
        answer = v[v.size()-1] - p;
    }

    printf("%lld", answer);
    return 0;
}