[백준]Baekjoon2805(이진탐색)

문제링크 : https://www.acmicpc.net/problem/2805

풀이

절단기에 설정할 수 있는 높이의 최댓값을 구하기 위해 높이를 하나하나 넣어주면서

비교를 해 주어야 하는데 전수조사를 하면 복잡도가 너무 높기 때문에

이진탐색을 사용해 준다.

범위중에 가장 작은 수인 1을 left, 주어진 나무의 높이중 가장 높은것을 right로 하여

이진탐색을 진행하게 된다.

#include <iostream>

using namespace std;

long long tree[1000000];
int N;
long long M;

bool cut(long long num)
{
	long long result = 0;
	for (int i = 0; i < N; i++) { 
		if (tree[i] > num) {
			result += (tree[i] - num); //num의 높이로 자른 나머지들을 모두 합산
		}
	}
	if (result >= M) return true; //만약 원하는 나무의 길이와 같거나 길면 true
	else return false; //짧으면 false
}
int main()
{
	scanf("%d %lld", &N, &M);
	long long max = 0;
	for (int i = 0; i < N; i++) {
		scanf("%lld", &tree[i]);
		if (tree[i] > max) max = tree[i];
	}
	long long first = 1; long long last = max;
	long long answer = 0;
	while (first <= last)
	{
		long long mid = (first + last) / 2;
		if (cut(mid)) {
			if (mid > answer) answer = mid;
			first = mid + 1;
		}
		else
			last = mid - 1;
	}
	printf("%lld\n", answer);
}