[2805] 나무 자르기

 

---

이게 왜 실버 2에 있지? 싶을 정도로 쉬운 문제였다.

내 자존감 지키미. 고마웡.

 

 

절단기 설정 높이를 KEY라고 지정해놓았다면,

나무가 X미터일 때 KEY 이상으로는 다 잘라서 가져간다는 뜻이다.

나무가 KEY보다 작으면 뭐 어쩔 수 없지 못가져가는 것이다.

 

 

그럼 이제 절단기 설정 높이의 범위를 알아야 하는데, 문제에 써있다.(0이상 1,000,000,000미만)

하지만 탐색 시간을 줄이기 위해 입력된 나무의 최대 높이를 최댓값으로 잡아주었다.

 

 

탐색시간을 줄이려면 이분 탐색이 짱이다. 사실 알고리즘 분류에도 이분 탐색이라고 쓰여있다.

완성된 코드는 아래와 같다. 주석을 자세히 적어놓았다.

#include <iostream>
using namespace std;

int N, M; 
int A[1000000];
int maximum = -1;
// 절단기 설정 값은 0 ~ 최대 max(A)

void BinarySearch(int start, int end) {
	if (start > end)return;

	int key = (start + end) / 2; // 절단기에서 설정할 수 있는 높이의 최댓값

	long long int sum = 0; // 나무의 길이가 2,000,000,000일 수 있기 때문에 큰 자료형
	for (int i = 0; i < N; i++)
	{
		if (A[i] - key >= 0) { // 자르고 그 위에 있는 것들 가져갈 수 있음
			sum += A[i] - key; // 가져갈 수 있는 나무를 구함

		}
	}
	
	if (sum >= M) { // 적어도 M미터의 나무를 구했다면
		maximum = (key > maximum) ? key : maximum; // 이 key가 최댓값인지
		BinarySearch(key + 1, end); // 더 큰 값을 위해 오른쪽 부분 탐색
	}
	else {
		BinarySearch(start, key - 1); // 못 구했다면 더 많이 잘라야 함. 그러려면 절단기 설정 높이가 더 낮아야함
	}
	
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M;
	int maxi = -1;
	for (int i = 0; i < N; i++)
	{
		cin >> A[i];
		maxi = (A[i] > maxi) ? A[i] : maxi;
	}


	BinarySearch(0, maxi);

	cout << maximum;

}