BOJ 백준 [2805] 나무 자르기

나무 자르기 문제

---

IDEA

N의 최댓값은 1,000,000이며 M의 최댓값은 2,000,000,000이다. 

가능한 모든 높이의 길이를 탐색하여 답을 구하고자 한다면, 1,000,000 * 2,000,000,000 즉, 주어진 시간제한을 넘길 것이다.

 

이를 해결하기 위해서 좀 더 생각을 해보자. 

나무가 나열된 순서는 상관이 없다. 그렇다면 나무를 순서내로 나열 시켜보자.

 

나무 정렬

 위와 같이 나무를 정렬 시켰을 때, 자르고자 하는 나무의 높이를 이분탐색하여 찾는다고 생각해보자.

우선, 나무를 정렬시키는데 사용되는 시간은 NlogN --> 1,000,000*lg1,000,000 약, 20,000,000의 시간이 소요된다.

그리고 이분탐색을 이용하여 높이의 최댓 값을 탐색해보자. NlogM --> 1,000,000*lg2,000,000,000 약, 30,000,000의 시간이 소요된다. 즉 시간 복잡도는 

NlogN+NlogM이므로 대략 1초의 시간안에 해결이 될것으로 보인다.

 

---

SOLVE

for (int i = 0; i < N; i++) {
        scanf("%d", &trees[i]);
}
 
sort(trees, trees + N);
    
int st = 0, en = 2000000000;
int mid = (st + en) / 2;
 
while (st <= en) {
    if (slice(mid) == 1) {
        st = mid + 1;
    }
    else {
        en = mid - 1;
    }
    mid = (st + en) / 2;
}

먼저 이분탐색을 통해 적합한 높이를 탐색하는 알고리즘을 구현해주자.

slice 함수의 경우, M이상의 나무를 자르게 된다면 1을 반환하도록 한다. 그래서 만약, 1이 반환이 된다면, 절단 높이를 더 높이자. 그렇지 않다면, 절단 높이를 더 낮추어야 한다.

int slice(int target) {
    long long int sum = 0;
 
    for (int i = N-1; i >= 0; i--) {
        int temp_slice = trees[i] - target;
        if(temp_slice > 0) {
            sum += temp_slice;
        } else {
            break;
        }
    }
 
    if (sum >= M) {
        return 1;
    } else {
        return 0;
    }
}

위와 같이 기준 절단 높이만큼 나무를 잘랐을 때, M이상이 모인다면 1을 반환하자.

 

---

SUCCESS