[백준][2805번][이분탐색] 나무 자르기

나무자르기

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

<코드>

#include <stdio.h>
 
long long tree[1000001];
 
int main(void){
 
    long long M, N;
    long long max = 0;
    long long left, right;
    long long result = 0;
    scanf("%lld %lld", &N, &M);
 
    for (int i = 0; i < N; i++){
        scanf("%lld", &tree[i]);
        if (max < tree[i])
            max = tree[i];
    }
    left = 0; right = max;
 
    while (left <= right){
        long long mid = (left + right) / 2;
        long long total = 0;
        for (int i = 0; i < N; i++)
            if (mid < tree[i])
                total += tree[i]-mid;
 
        if (total >= M){
            if (result<mid)
                result = mid;
            left = mid + 1;
        }
        else{
            right = mid - 1;
        }
 
    }
 
    printf("%lld\n", result);
 
    return 0;
}

<문제 푼 요령>

 1. 유추한 정답 후보로 -> 문제에 대입해서 가장 적당한 정답값을 이끄러내는 방법이다.

 2. 정답 후보를 유추하는 과정에서 이분탐색을 사용하였다. 

 3. 초기 left는 0이고 right는 tree들의 max 값으로 한다. 그 후에 이분탐색으로 정답 후보를 뽑고 그 후보로 나무를 잘라서 우리가 필요한 통나무 길이인 M과 비교한다.

 4. 비교한 값이 M이 더 크다면 우리는 작은값을 탐색해야하고 M보다 우리가 잘라낸 나무가 더 크다면 결과값을 저장한 후 더 큰 값을 탐색해서 정답을 유추한다.