[BaekJoon] 2805.나무 자르기

BeakJoon Online judge

[2805] 나무 자르기

1. Let’s Think

1. 첫번째 Idea

단순하게 생각해서 순차적으로 적정 높이를 찾아보고자하였다. 하지만 해당 아이디어의 경우, 나무의 최대 높이가 2,000,000,000 즉, 최대 2 * (10^9)의 Time Complexity가 소요된다.
약 2초의 시간이 소요되므로 시간제한에 걸린다.

 	int ans = 0, getH = INT_MAX;
	 for(int H = MaxH; H >= 0; H--){//MaxH : 주어진 나무의 최대 길이
     	int temp = 0;
        for(int i = 0; i < N; i++) {
        	temp += max(0, arr[i] - H);
        }
        if(temp >= M) {
        	if(getH > temp) {
            	getH = temp;
                ans = H;
            }
        }
     }
     printf("%d", ans);

2. 두번째 Idea

그렇다면 나무의 높이를 기준으로 문제를 푸는 것 대신, 주어진 나무높이를 기준으로 문제를 풀어보자.
또한, 주어진 나무의 갯수의 최대수를 고려해보면 완전탐색의 방법(Time Complexity -> O(N^2))의 경우 또한 시간 초과가 될것이다.
그러면, 이분탐색을 통해 문제를 해결하여 보자. 만약 이분탐색을 통해 문제를 해결한다면, O(NlogN)의 Time Complexity가 소요될 것이다. N의 최대값의 경우 10^6이므로 NlogN –> 10^6 * log(10^6) ≒ 19931568 즉, 제한 시간내에 문제가 해결된다.

    int slice(vector<int>& arr, int H) {
    	int ans = 0;
        for(int h : arr) {
        	ans += max(h - H, 0);
        }
        return ans;
    }
    int main(void) {
    	....
		int ans = 0;
    	sort(arr.begin(), arr.end());
    	int s = 0, e = N - 1;
    	while(s <= e) {
    		int m = (s + e)/2;
        	if(slice(arr, arr[m]) >= M) {
        		s = m + 1;
        	}
        	else {
        		e = m - 1;
        	}
    	}
    	printf("%d", arr[e]);
        ....
    }

다만 해당 아이디어에는 문제점이 존재한다.
만약, 주어진 나무의 높이가 아닌 값이 답이 된다면 어떻게 하지?
예시를 한번 살펴보자.

arr = [1, 2, 3, 7, 8] M = 4
s = 0, e = 4 → m = 2
slice(arr, 3) = 0, 0, 0, 4, 5 → ret = 9
s = 3, e = 4 → m = 3
slice(arr, 7) = 0, 0, 0, 0, 1 → ret = 1
즉, 해당 알고리즘에서는 정답이 3이된다.
하지만 해당 예제의 정답은 5이다.

3. 세번째 Idea

그러면 0부터 나무의 최댓값사이를 이분 탐색으로 탐색하여 원하는 결과 값을 계산해보자.
이때, TIme complexity의 경우 나무의 최대 높이를 H라고 했을 때, O(NlogH)가 된다. H의 max값은 10^9이므로 10^6 * lg 10^9 ≒ 29,897,352 즉, 주어진 시간내에 문제가 해결가능하다.

    int slice(vector<int>& arr, int H) {
    	int ans = 0;
        int N = arr.size();
        for(int i = N - 1; i >= 0; i--) {
        	if(arr[i] - H <= 0) break;
            ans += arr[i] - H;
        }
        return ans;
    }
    int main(void) {
    	....
		int ans = 0;
    	sort(arr.begin(), arr.end()); // sort알고리즘의 시간 복잡도는 nlgn이다.
    	int s = 0, e = arr.back();
    	while(s <= e) {
    		int m = (s + e)/2;
        	if(slice(arr, m) >= M) {
        		s = m + 1;
        	}
        	else {
        		e = m - 1;
        	}
    	}
    	printf("%d", e);
        ....
    }

2. Solve the Problem

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
long long int slice(vector<int>& arr, int H) {
	long long int ans = 0;
    int N = arr.size();
	for (int i = N-1; i >= 0; i--) {
		if(arr[i] - H <= 0) break;
        ans += arr[i] - H;
	}
    return ans;
}
int main() {
    int N, M;
	scanf("%d %d", &N, &M);
	vector<int> arr(N);
    for (int i = 0; i < N; i++) {
		scanf("%d", &arr[i]);
    }
	sort(arr.begin(), arr.end());
	
	int s = 0, e = arr.back();
    while(s <= e) {
    	int m = (s + e)/2;
       	if(slice(arr, m) >= M) {
       		s = m + 1;
       	}
       	else {
       		e = m - 1;
       	}
    }
    printf("%d", e);
    return 0;
}

3. End

4. Plus

위의 문제풀이에서 slice함수의 경우 O(N)의 시간이 소요된다. 이를 한번 줄여보자. 먼저, 나무의 길이들을 합할 array를 생성해서 합들을 구한다.

 int N = arr.size();
 vector<long long> sums(N, 0); //나무의 최대길이 - 10^9, 최대 갯수 - 10^ 6 --> 10^15 : long long 의 범위안에 든다.
 sums[0] = arr[0];
 for(int i = 1; i < N; i++) {
 	sums[i] = sums[i - 1] + (long long)arr[i];
 }

lower bound나 upper bound를 활용하여 arr에서 target나무 길이인 H보다 크거나 같은 나무의 갯수를 구한다. 또한 미리 구해둔 sums array를 활용하여 H높이에서 나무를 잘랐을 때, 잘라지는 나무들의 길이의 합을 구한다. 그러면 상근이가 구하는 나무의 길이를 알 수 있다.

    auto idx = lower_bound(arr.begin(), arr.end(), H) - arr.begin();
    int count = N - idx;
    long long h = sums[N - 1] - sums[idx - 1];
    long long ans = h - (long long)count * (long long)H;//곱셈 중에 integer범위를 넘어 설수 있으니 미리 형변환을 해주었다.

해당 방법을 사용한다면 sums를 구하는데 O(N) 나무의 길이를 계산하는데 O(lgN)을 사용하게된다.
따라서 O(N + lg(maxH) * lg(N) + NlogN//정렬) 이 된다.