06.01. 나무 자르기 [Binary Search & Parametric Search][백준 2805]

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

2805번: 나무 자르기

 

Algorithm classification : Binary Search, Parametric Search

 

06.01.1. Problem

Lumberjack Mirko needs to chop down M metres of wood. It is an easy job for him since he has a nifty new woodcutting machine that can take down forests like wildfire. However, Mirko is only allowed to cut a single row of trees.

 

Mirko's machine works as follows: Mirko sets a height parameter H (in metres), and the machine raises a giant sawblade to that height and cuts off all tree parts higher than H (of course, trees not higher than H meters remain intact). Mirko then takes the parts that were cut off. For example, if the tree row contains trees with heights of 20, 15, 10, and 17 metres, and Mirko raises his sawblade to 15 metres, the remaining tree heights after cutting will be 15, 15, 10, and 15 metres, respectively, while Mirko will take 5 metres off the first tree and 2 metres off the fourth tree (7 metres of wood in total).

 

Mirko is ecologically minded, so he doesn't want to cut off more wood than necessary. That's why he wants to set his sawblade as high as possible. Help Mirko find the maximum integer height of the sawblade that still allows him to cut off at least M metres of wood.

 

 

06.01.2. Input limit

The first line of input contains two space-separated positive integers, N (the number of trees, 1 ≤ N ≤ 1 000 000) and M (Mirko's required wood amount, 1 ≤ M ≤ 2 000 000 000).

 

The second line of input contains N space-separated positive integers less than 1 000 000 000, the heights of each tree (in metres). The sum of all heights is greater than or equal to M, thus Mirko will always be able to obtain the required amount of wood.

 

 

06.01.3. Output

The first and only line of output must contain the required height setting.

 

 

06.01.4. Solution

높이가 다른 나무가 N개 있을 때, 모든 나무를 H만큼 남겨놓고 자른 부분을 가져가는 문제입니다. 이때 가져가는 나무의 길이 합이 M 이상되게 하는 H 중 최댓값을 구하는 문제입니다. H가 커지면 가져갈 수 있는 나무의 길이 합은 줄어들고 반대로 H가 작아지면 가져갈 수 있는 나무의 길이 합은 증가합니다. 즉, 단조함수라는 의미입니다. 따라서 이분 탐색을 적용할 수 있습니다.

 

조금 더 엄밀(? : 사실 엄밀한지도 모르겠군요)하게 말씀드리자면 고등학교 수학 시간에 배운 Rolle's theorem이나  Intermediate value theorem이 생각나시나요? 한국어로 중간값 정리 또는 사이값 정리는 구간에 정의된 연속 함수가 임의의 두 함숫값 사이의 모든 수를 함숫값으로 포함한다는 정리입니다. 물론 존재성을 보이는데 그치긴 하지만 단조함수라는 것은 별도로 증명하면 되니까요.(함수값을 배열이라고 생각하고 정렬되어 있음을 증명하면 될 것입니다.) 

 

The intermediate value theorem states the following:

• Consider an interval I = [a, b] of real numvers and a coninuous function f : I → R. Then if u is a number between f(a) and f(b), that is, min(f(a), f(b)) < u < max(f(a), f(b)), then there is a c(a < c < b) such that f(c) = u
• The image set f(I) is also an interval, and it contains [min(f(a), f(b)), max(f(a), f(b))]

 

중간값 정리의 증명은 생략하겠습니다.

 

이분 탐색과 매개변수 탐색을 설명해드렸던 포스팅에서 가져온 코드인데요. 이 의사코드가 어떻게 바뀔지 살펴보겠습니다.

LEFT = MIN VALUE, RIGHT = MAX VALUE; 
WHILE(LEFT <= RIGHT){ 
	MID = (LEFT + RIGHT) / 2; 
    
    CHECK; 
    
    UPDATE : LEFT = MID + 1 OR RIGHT = MID - 1; 
    
    STORE TEMP RESULT; 
}

이분 탐색을 이용한 매개변수 탐색을 이 문제에 적용한다면 LEFT와 RIGHT가 적절하게 정해진다면 양 끝점의 조건 만족 vs 불만족 여부가 다르기 때문에 반드시 [LEFT, RIGHT] 내에 답이 존재한다는 것을 알 수 있습니다. CHECK는 나무가 N개이니 O(N) 시간복잡도만 필요할 겁니다. 영역의 범위가 1이 되면 답은 결정되겠죠. 물론 중간에 결과를 저장해야하는 문제도 있습니다. 이 코드를 활용하면 조건을 만족하는 최댓값과 조건을 불만족하는 최솟값을 모두 계산할 수 있습니다. 사실 조건을 불만족하는 최솟값은 당연히 조건을 만족하는 최댓값에서 1을 더한 값이겠지만요.

 

#include<stdio.h>
int main(){
	int n, m, i, left = 0, right = 1000000000, mid;
	scanf("%d %d", &n, &m);
	int a[n];
	
	for(i = 0; i < n; i++){
		scanf("%d", &a[i]);
	}
	long long temp; 
	while(left <= right){
		mid = (left + right) / 2;
		temp = 0;
		for(i = 0; i < n; i++){
			if(a[i] >= mid) temp += (a[i] - mid);
		}
		
		printf("%d %d : %d > %d\n", left, right, mid, temp);
		if(temp < m){
			right = mid - 1;
		}
		else{
			left = mid + 1;
		}
	}
	printf("%d", right);
	
	return 0;
}

나무의 높이가 최대 10억이니 최대 몇 번 시도할지 확인할 수 있을 겁니다. 나무 높이의 최대값을 RIGHT로 둔다면 시간복잡도는 O(N * log(max(H)))이 되겠죠. 

 

한가지 더 중요한 점은 UPDATE 조건입니다. 방향을 바꾸면 결과는 달라지겠죠. 조건을 만족하는 최솟값을 구할 수도 있을 겁니다. 물론 이분 탐색 알고리즘의 개념은 동일하게 적용됩니다. 

 

 

이분 탐색과 매개변수 탐색 이론 설명 포스팅에서 문제를 풀 때 long long 자료형을 사용하시길 권고드렸었는데요. 추가적인 tip을 드리자면 백준 online judge 질문 page를 보시면 corner case를 get하실 수 있습니다. LEFT와 RIGHT의 범위를 좁게 주기 위해 Input limit에 따라 고정하지 않고 Input에 따라 범위를 준다면 corner case에서 잘못된 값을 출력할 수도 있습니다. 생각해보니 이분 탐색이여서 굳이 범위를 좁게 해주는 최적화가 큰 의미가 있을까 싶기도 하네요.

 

도움이 되시라고 몇 개의 test case를 아래에 남겨두겠습니다.

6 15
2 11 3 10 5 20
>> 8

2 11
10 10
>> 4

3 1
1 2 2
>> 1

4 10
1 4 5 7
>> 2

5 2000000000 
900000000 900000000 900000000 900000000 900000000
>> 500000000

6 12
19 9 18 20 17 8
>> 15

5 14
4 22 10 16 36
>> 22