[백준] No.2805 - 나무 자르기 (C++)

EVEerNew 2021. 1. 10. 18:27

2805번: 나무 자르기

첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보

www.acmicpc.net

solved.ac 난이도: Silver 3

이분 탐색의 응용인 parametric search를 이용하는 대표적인 문제이다.

이분 탐색(binary search)과 parametric search의 차이점은 라몽님의 게시글을 참조하자.

left는 0에서부터 right는 가장 긴 나무의 길이에서부터 시작한다.

mid( = (left +right) /2 )를 나무를 자르는 높이라고 하면 잘린 나무들의 길이 cut_sum을 구할 수 있다.

1. cut_sum이 필요한 나무보다 작을 때

mid값을 더 낮춰야 잘린 나무들의 길이가 커진다.

따라서 right = mid -1로 설정해준다.

2. cut_sum이 필요한 나무보다 크거나 같을 때

만약 cut_sum이 크다면 mid 더 높여서 가장 긴 높이를 구해야 한다.

따라서 left = mid +1로 설정해준다.

만약 cut_sum이 정확히 필요한 나무길이와 일치한다면 동일하게 left = mid +1을 진행할 경우

cut_sum이 항상 작게 되어 1번 경우가 지속적으로 선택될 것이다.

따라서 answer변수를 선언하여 answer < mid인 경우 해당 mid를 answer로 저장해 두자.

크거나 같은 경우를 함께 구현하는 이유는

4 4
20 15 10 17

와 같은 경우를 처리하기 위해서이다.

4 이상의 길이를 얻을 수 있는 최대 높이는 16이다.

하지만 (20-16) + (17-16) = 5로 필요한 길이 4와 같지는 않다.

17일 때는 (20-17) = 3으로 4보단 부족하다.

즉, 정확히 cut_sum과 필요한 나무의 길이가 일치한다는 보장은 할 수 없으므로

크거나 같은 경우는 아래의 코드처럼 같이 처리해주어야 한다.

1
2
3
4
5
6
7

if(cut_sum < need_len){
  right = mid -1;
}else{
  left = mid +1;
  if(answer < mid)
    answer = mid; 
}

cs

추가적으로 해당 문제의 cut_sum은 int형의 범위를 초과할 수 있으므로 long long으로 선언해주자.

본인은 left의 시작 값을 0이 아닌 가장 작은 나무의 길이로 선언하여 틀렸다...

다음 parametric search문제로는 백준 - 숫자구슬(2613)을 추천한다.

	#include <iostream>
	#include<vector>
	using namespace std;

	int tree_num;
	long long need_len;
	vector<int> tree_height;

	int main() {
	ios_base::sync_with_stdio(0);
	cin>>tree_num>>need_len;

	int temp,left= 0,right=0;
	for(int i=0; i<tree_num ; ++i){
	cin>>temp;
	tree_height.push_back(temp);
	right = max(right, temp);
	}

	long long cut_sum=0;
	int mid,answer=0;
	while(left<= right){
	cut_sum=0;
	mid = (left +right) /2;

	for(int i=0; i<tree_num ; ++i){
	if(tree_height[i] >mid)
	cut_sum += (long long)(tree_height[i] - mid);
	}

	if(cut_sum < need_len){
	right = mid -1;
	}else{
	left = mid +1;
	if(answer < mid)
	answer = mid;
	}
	}

	cout<<answer<<'\n';
	return 0;
	}