[2805]나무자르기(C++)

1. 문제

www.acmicpc.net/problem/2805

2805번: 나무 자르기

2. 접근 방법

 

 

1) 톱의 높이로 가능한 범위는 '~ 나무의 가장 높은 높이' 이다. 

 

2) 톱의 높이를 정했을 때, 높이를 구하기 위해서는 log(N)만큼이 필요하다.(모든 나무들들을 다 베어서 합을 구해야 하므로), 따라서 모든 나무들의 높이에 맞게 나무를 잘라본다면 log(N^2)만큼 걸리므로 시간초과가 걸린다.

 

3) 이처럼 나무의 개수도 많고, 값도 크면 이분 탐색을 고려해 보도록 생각의 흐름을 바꿔야 했다.

 

4) 처음엔 STL을 좋아하는 나는 binary_search함수를 사용하려 했다. 그런데 STL함수는 단순히 값이 있는지, 없는지만을 bool 값으로 반환하고, 막상 binary_search를 돌 array를 구하기 위해선 log(N*N)만큼 구해야 했다. 이 뿐만 아니라 binary_search할 값을 무엇으로 해야 할지 고민이 되었다.(M으로 해야 하는지, 톱의 높이값으로 해야 할지)

따라서 직접 이분탐색을 통해 "톱의 높이"를 구해야 한다.

 

5) 이분 탐색을 위해서 필요한 변수 3개 : low(높이 범위의 가장 낮은 값), high(높이 범위의 가장 높은 값), mid(low와 high의 중간값)을 선언한 후, 톱의 높이가 mid일 때 구한 나무의 길이가 M보다 많은지를 판단한다.

 

6) 여기서 중요한 점은, 톱으로 잘라서 얻은 나무의 총 길이가 반드시 M과 맞아 떨어지지 않을 수 있으며, 가능한 톱의 높이가 여러개 일 때, 최대한 "높은"높이로 구해야한다. 따라서 조건을 만족하더라도 계속 mid+1을 통해 가능한 높이의 최댓값을 구한다.

 

3. 실수했던 부분 & 처음 알았던 부분

1) v.reserve()와 v(N)의 차이

 - v.reserve(N) 후에는 v.push_back()으로 값을 삽입해야 한다.

 - v(N)으로 선언과 동시에 초기화 했을 경우에는 cin >> v[i]로 해야 처음부터 들어간다. v.push_back으로 값을 넣으면 v[N]부터 값이 들어간다.

 

2) answer = 0 초기화 안함,, 나무를 구할 수 없는 경우 0을 리턴해야 한다.

 

3) low = 1과 low = *min_element(tree.begin(),tree.end()) 차이

- low = min_element로 하면 안됨!!! 모든 나무를 다 잘라야 할 수도 있기 때문 

4. 코드

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<long long>tree;
long long N,M;

bool possible(long long height) {

	long long len = 0;
	for(int i=0;i<N;i++) 
	 	if(tree[i] > height)
		 	len += (tree[i] - height);
	
	if(len >= M) return true;
	else return false;
}


int main() {
 	ios_base::sync_with_stdio(0);
	cin.tie(0);

	long long answer=0,tmp;
	cin >> N >> M;
	
	for(int i=0;i<N;i++) {
		cin >> tmp;
		tree.push_back(tmp);
	}

	long long high = *max_element(tree.begin(),tree.end());
	long long low = 1;

	while(low <= high ) {
		long long mid = (low + high)/2;
		if(possible(mid)) {
			answer = max(answer,mid); //조건을 충족하는 높이 중 가장 높은 값을 구해야 하므로 
			low = mid+1;
		}
		else high = mid-1;
	}
	cout <<answer<<endl;
	return 0;
}