[백준알고리즘] 2516번 예산

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

미쳤다 나는 아무리 생각해도 내방법으로 푸는 거 밖에 생각 못했는데 진짜 답 보니까 충격적이다

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

물론 내 방법도 sort를 해야한다는 것이 엄청 좋은 방법은 아니었지만 ㅠ

답 보니까 헉 소리나옴

제대로 된 정답은 따로 안 올린당... 힌트는 이분탐색으로 푸는 거라는 거..

밑에는 내가 짰던 코드!!

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<iostream>
using namespace std;
 
vector <int> arr;
 
int main(void)
{
    int N;
    int M;
 
    int value = 0; //  값
    int sum = 0; // 부분 누적 합
    int max_value = 0; // 상한액
    int sum_value = 0; // 전체 누적 합
 
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &value);
        arr.push_back(value);
 
        // 가장 큰 값 저장해두기
        if (max_value < value) max_value = value;
        // 다 합친 값 저장해두기
        sum_value += value;
    }
 
    scanf("%d", &M);
 
    // 할당할 수 있는 예산보다 합친 값이 크면 상한액 구하기
    if (M < sum_value)
    {
        // 상한액은 평균에서부터 시작
        max_value = M/N;
 
        // 배열을 오름차순으로 정렬
        sort(arr.begin(), arr.end());
 
        // 배열의 값을 누적해가며 현재까지 배정될 수 있는지 확인
        for (int i = 0; i < N; i++)
        {
            // 상한액 누적
            sum += arr[i];
 
            // 배열의 값이 이전에 구해놓은 상한액보다 크면 상한액을 갱신할 수 없다.
            if (arr[i] > max_value) break;
            // 현재까지 누적하여 구한 상한액이 이전 배열 값보다 크거나 같으면 상한액을 갱신
            else
            {
                max_value = (M - sum) / (N - (i+1));
            }
        }
    }
 
    printf("%d\n", max_value);
 
    return 0;
}