2805 나무 자르기

일정 높이 이상의 나무들을 다 잘랐을 때,

자연을 보호하면서 얻을 수 있는 나무도 챙기는 효율적인 방법 구하기

1. 문제

---

간단 설명

벌목기는 H 이상 높이의 나무들을 모두 자른다

왼쪽부터 차례로 20, 15, 10, 17의 나무가 있고

벌목기의 높이를 15로 설정했다면

5, 0, 0, 2 만큼 총 7의 나무를 얻을 수 있다

벌목기의 높이를 10으로 설정했다면

10, 5, 0, 7 만큼 총 22의 나무를 얻을 수 있지만,

자연을 보호해야하므로 필요한 만큼만 잘라야한다

2. 문제 분석

---

필요변수

나무 개수 int N (1 ≤ N ≤ 1,000,000)

원하는 나무의 길이 int M (1 ≤ M ≤ 2,000,000,000)

나무의 정보들을 저장할 배열 vector<int> trees

높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0 이므로, int형에 저장

주의점

• 자료형과 시간초과에 주의할 것

알고리즘

1. 완전 탐색으로 접근
   • 가장 큰 나무에서 1씩 줄어들면서 구하는 방법으로 접근
   • worst case : 100만개의 나무 중 하나만 1,000,000,000 이고, 나머지는 1인 경우
   • 10억 * 100만으로 1초 안에 불가능
2. 이분 탐색으로 접근
   • 가장 큰 나무를 구하고, 이분탐색으로 접근한다
   • 가장 큰 나무의 절반값으로 잘랐을 때, 얻을수 있는 나무의 길이를 목표값과 비교
   • 목표값보다 크다면 H를 더 올린다 <- 자연 보호
   • 목표값보다 작다면 H를 더 내린다 <- 더 잘라야함

1. N과 M을 입력받는다
2. N개의 나무를 입력받으면서 가장 큰 나무의 길이를 저장해둔다
3. 0부터 가장 큰 나무 사이의 범위에서 M을 목표값으로 하는 이진 탐색을 수행한다
    3-1. 중간값을 구하고, 이 값으로 나무를 잘랐을 때 얻을수 있는 나무 길이를 구한다
    - 이 값은 int값을 초과할 수 있으므로 주의
    3-2. 얻은 나무 길이와 목표값을 비교한다
    3-3. 목표값보다 크다면 end를 수정해 H를 더 올린다
    3-4. 목표값보다 작다면 start를 수정해 H를 더 내린다
4. 이분탐색이 종료되면 end값을 리턴한다
    - 목표값이 딱 안떨어질수도 있다
    - ex) 3, 3, 5, 5 의 나무에서 M=3을 구하는경우 
5. 이를 출력 후 종료

3. 소스코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, M;
vector<int> trees;

int my_binary_search(int start, int end, int target) {

	int mid;
	while (start <= end) {
		mid = (start + end) / 2;
		
		// target과 mid로 잘랐을때 얻을수 있는 나무 값을 비교
		long long int sum = 0;
		for(int tree : trees){
			if (tree < mid) continue;
			sum += tree - mid;
		}
		// cout << "얻을수 있는 나무 길이 : " << sum << endl;
		if (sum == target) {
			return mid;
		}
		// 얻을수 있는 나무 길이가 target보다 작다면, H를 높인다 
		else if (sum < target) {
			end = mid - 1;
		}
		// 얻을수 있는 나무 길이가 target보다 크다면, H를 내린다 
		else if(sum > target){
			start = mid + 1;
		}
	}
	return end;
}

int main() {
	freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> N >> M;
	trees.resize(N);
	
	int max_tree = 0, min_tree = 21e8;
	for (int i = 0; i < N; i++) {
		cin >> trees[i];
		max_tree = max(max_tree, trees[i]);
	}

	cout << my_binary_search(0, max_tree, M); // H의 범위는 0에서 가장 큰 나무 까지다 

	return 0;
}

---