[백준] 2805 C++ 나무 자르기 [이분 탐색]

- 문제 설명

 

- 문제 풀이

이분 탐색을 활용해야 하는 문제다. 예제 1과 같이 4개의 나무, 7의 길이 만큼 가져가야 할 때를 예로 들어보자.

이분 탐색을 위해 최소 잘라내는 수 1 = s, 최대 자를 수 있는 길이를 나무중에 제일 큰 나무(20 = e)라고 해보자.

그럼 그 중간값 mid = (s + e) / 2 를 기준으로 잘라낸다.

잘라낸 길이의 합이 가져가야 할 길이 7보다 크다면 mid값을 높여아 하기 때문에 s = mid + 1로 , ans = mid 갱신

(마지막은 항상 7만큼 혹은 그보다 더 가져가야 할 것이므로 정답을 mid로 갱신)

잘라낸 길이의 합이 가져가야 할 길이 7보다 작다면 mid값을 낮춰야 하기 때문에 e = mid - 1

s 가 e보다 커질때 까지 반복한 후 그 순간 mid값이 잘라야 하는 높이의 최댓값이 된다.

s = 1 ,e = 20

mid = (1 + 20) / 2 = 10

-> 길이의 합  22 >= 7

-> s = mid + 1 = 11

ans = mid = 10

 

 

s = 11, e = 20

mid = (11 + 20) / 2 = 15

-> 길이의 합  7 >= 7

-> s = mid + 1 = 16

ans = mid = 15

 

 

s = 16, e = 20

mid = (16 + 20) / 2 = 18

-> 길이의 합  2 >= 7

-> e = mid - 1 = 17

 

 

s = 16, e = 17

mid = (16 + 17) / 2 = 16

-> 길이의 합  5 >= 7

-> e = mid - 1 = 16

 

 

s = 16, e = 16

mid = (16 + 16) / 2 = 16

-> 길이의 합  5 >= 7

-> e = mid - 1 = 15

 

이 때 s(16)가 e(15)보다 커지므로 종료

따라서 ans = 15로 마무리 된다.

 

 

 

- 코드

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

int N, M, s, e, ans;
long long sum_tree = 0;
int trees[1000000];

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

	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		cin >> trees[i];
	}

	s = 1;
	e = *max_element(trees, trees + N);

	while (s <= e)
	{
		int mid = (s + e) / 2; // 중간값 -> 이분 탐색을 위해
		sum_tree = 0;
		for (int i = 0; i < N; i++)
		{
			if (trees[i] <= mid)
				continue;
			sum_tree += trees[i] - mid; // mid높이를 기준으로 잘랐을 때 잘린 나무들의 총 길이의 합
		}
		if (sum_tree >= M) // 잘린 나무의 합이 가져가려 하는 나무길이보다 크거나 같다면
		{
			s = mid + 1; // mid값을 높여서 잘린 나무의 합을 낮추기 위해
			ans = mid; // 마지막은 항상 M만큼 혹은 그보다 더 가져가야 할 것이므로 답을 mid로 갱신
		}
		else if(sum_tree < M) // 잘린 나무의 합이 가져가려 하는 나무길이보다 작다면
		{
			e = mid - 1; // mid 값을 낮춰서 잘린 나무의 합을 높이기 위해
		}
	}

	cout << ans;

	return 0;
}