[BOJ 2805] 나무 자르기

 

문제 출저 : https://www.acmicpc.net/problem/2805

 

풀이 : 

 

이분 탐색 문제입니다.

절단기 높이의 최댓값은 나무 높이 들 중 최댓값이 됩니다.

기본적인 이분 탐색은 [2512] 예산 과 같으니 참고 하시면 감사하겠습니다.

그리고 나무의 최대 높이가 20억이니 꼭 결과값 저장할 때 long long int 같이 큰 정수 써주셔야합니다.

처음에 아무생각 없이 안썼다가 틀렸었습니다 .ㅠㅠ

 

#include<stdio.h>
 
int n, m, arr[1000000], Max, result;
 
void parametricSearch(int s, int e)
{
    if (s>e)return;
    long long int ret = 0;
    int mid = (s + e) / 2;
    for (int i = 0; i < n; i++)if (arr[i] > mid)ret += arr[i] - mid;
    if (ret >= m)
    {
        if (result < mid)result = mid;
        parametricSearch(mid + 1, e);
    }
    else parametricSearch(s, mid - 1);
}
 
int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);
        if (arr[i] > Max)Max = arr[i];
    }
    parametricSearch(0, Max);
    printf("%d", result);
}