2805번_나무 자르기_BOJ

문제 링크

2805번 나무 자르기 : https://www.acmicpc.net/problem/2805

문제 설명 및 해결 아이디어

나무의 수 N은 1이상 1,000,000이하이다. 그리고 가져갈 나무의 길이 M은 1이상 2,000,000,000이하이다. 

가장 간단하게 완탐을 하게 되면 O(NM)이 되어 시간초과가 난다.

이를 효율적으로 하기위해 Parametric Search로 해결할 수 있다.

그리고 이 문제의 비교함수 y=f(x)의 관계를 생각해보면, 다음과 같다.

즉, SUM이 커질수록 가져갈 나무의 길이 M이 작아지는 관계이다.

이를 잘 생각하여 코드를 작성해야한다.

코드

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define ll long long int
ll n, m, num, res;
vector<ll> namu;
 
ll func() {
    ll left = 1, right = 2000000000;
    ll ret = 0;
    while (left <= right) {
        ll mid = (left + right) / 2;
        ll sum = 0;
        for (int i = 0; i < n; ++i) {
            if (namu[i] < mid)
                sum += 0;
            else
                sum += (namu[i] - mid);
        }
 
        if (sum < m) {
            right = mid - 1;
        }
        else {
            left = mid + 1;
            ret = max(ret, mid);
        }
    }
    return ret;
}
 
int main() {
    scanf("%lld %lld", &n, &m);
    for (int i = 0; i < n; ++i) {
        scanf("%lld", &num);
        namu.push_back(num);
    }
    res = func();
    printf("%lld\n", res);
    return 0;
}