백준) 2805 나무 자르기

나무 자르기

 

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

 

 

시도해 볼 수 있는 높이는 모두 정수다.

 

따라서 모든 가능한 정수에 대해서 시도해보면, M보다 크거나 같은 결과가 나오는 높이들을 파악할 수 있고,  그 중 가장 큰 정수를 찾으면 된다.

 

 

하지만 모든 정수를 시도해 볼 필요는 없다.

 

만약 300의 높이로 시도해 보았을 때, M보다 작은 결과가 나온다면, 300보다 높은 높이로 시도했을 때도 당연히 실패할 것이기 때문이다.

 

 

따라서 가능한 결과들은 한 구간으로만 나올 것이다.

 

우리가 할 것은 그 구간을 빠르게 찾는 것이다.

 

 

이진 탐색으로 빠르게 구간을 찾을 수 있다. 

 

1/2 씩 구간을 줄여나가는 방벙으로, n개의 수를 로그시간에 탐색할 수 있다.

 

 

정수의 범위는 1부터 가장 높은 나무의 높이 까지다.

 

주어진 나무 높이의 합이 M보다 크다는 조건 때문에 1을 계산해볼 필요가 없다.

 

가장 큰 높이로 자르면 당연히 합이 0일 것이므로 계산해볼 필요가 없다.

 

 

이제부터 중간값으로 구간을 줄여보자.

 

중간 높이로 자르고 나면 두 가지 경우가 생긴다.

 

 

1. 잘린 나무의 합이 M보다 작을 경우

 

현재 높이보다 낮은 높이로 시도해 보아야 한다. 왼쪽 구간으로 변경

 

2. 잘린 나무의 합이 M보다 작거나 클 경우

 

현재 높이보다 높은 높이로 시도해 볼 수 있다. 오른쪽 구간으로 변경

 

 

이를 반복하다보면 구간의 제일 큰 정수 값을 알 수 있다.

 

코드로 옮기면 다음과 같다.

 

#include <stdio.h>
using namespace std;
 
int n, m;
long long tree[1000000];
 
bool chk(int mid) {
    long long sum = 0;
    for (int i = 0; i < n; ++i) {
        if (mid < tree[i])
            sum += tree[i] - mid;
    }
 
    return sum >= m;
}
 
int main() {
    scanf("%d %d", &n, &m);
 
    int max = 0;
    for (int i = 0; i < n; ++i) {
        scanf("%lld", &tree[i]);
        if (tree[i] > max)
            max = tree[i];
    }
 
 
    int left = 0, right = max;
    int ans = 0;
 
    while (left <= right) {
        int mid = (left + right) / 2;
 
        if (chk(mid)) {
            if (ans < mid)
                ans = mid;
            left = mid + 1;
        }
        else
            right = mid - 1;
    }
 
    printf("%d", ans);
 
    return 0;
}

 

나무의 높이들을 저장하는 배열을 정렬해 둔다면, 정수 값을 1씩 옮기지 않고 구간을 옮길 수 있으므로

 

최적화가 가능할 것 같다.