2805 나무 자르기

이 문제를 풀기 위해서 알아야 할 기법이 있는데, 파라메트릭 서치라는 기법이다.

이분탐색에서 파생된 방법으로 수치해석의 bisection method와 유사하다.

순차적인 선택지에서 절반씩 줄여서 해를 찾는 방법으로 해가 존재하지 않더라도, 근삿값을 찾는게 핵심이다.

이 방법의 강력한 점은 입력의 크기가 크더라도 탐색 횟수는 logN이기 때문에 효과적이라는 점이다.

조금 더 수치해석적으로 보면, bisection method의 단점은 지정된 범위 내에 해가 존재하지 않는다면, 해로 수렴하는 시간이 오래걸린다.

 

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략이란 책에서 이 문제에 대해 최적화 문제를 결정 문제로 바꾸기라는 파트로 나눠서 다루고 있고, 해당 구조로 바꾸는 방법도 소개하고 있다. 결정 문제라는 말이 생소하지만 결국 어떤 문제가 주어지면 결정 (Yes/No)하는 것과 같다. 또한 파라메트릭 서치의 개념도 이러한 결정 문제들에서 이분법을 사용한 빠른 탐색이 주가 된다.

 

이제 문제에 적용하여 생각해보자. 주어진 문제는 최적화 문제이기 때문에 파라메트릭 서치를 적용할 구조가 아니다.

그렇다면 어떻게 바꿔야 할까

 

이 문제에 적용시켜보면, 나무의 길이 M을 얻기 위한 높이 H를 얼마나 설정해야 하는가라는 문제를 높이를 H만큼 설정하면 나무의 길이 M을 얻을 수 있는가? 라는 문제로 바꾸어 생각해보면 된다.

 

H=1부터 생각해보자, 높이를 1로 설정하면 얻을 수 있는 나무의 길이는 M이상인가? (Y)

높이를 2로 설정하면 얻을 수 있는 나무의 길이는 M이상인가? (Y)

....

높이를 h로 설정하면 얻을 수 있는 나무의 길이는 M이상인가? (Y)

높이를 h+1로 설정하면 얻을 수 있는 나무의 길이는 M이상인가? (N)

 

이제 우리가 원하는 최댓값을 찾아보자. 나무의 길이 M이상을 최초로 얻을 수 없기 전의 높이 값이 최댓값이란걸 직관적으로 알 수 있다.

 

정답코드

#include <iostream>
#include <vector>
using namespace std;
int N, M;
bool Possible(const vector<int>& v, int height)
{
	long long sum = 0;
	for (const auto& s : v) {
		if (height >= s)
			continue;
		else
			sum += s - height;
	}
	if (sum >= M)
		return true;
	else
		return false;
}
void BinSearch(vector<int>& v)
{
	int left = 0;
	int right = 2000000000;
	int mid = (left + right) / 2;
	while (left <= right) {
		if (Possible(v, mid))
			left = mid + 1;
		else
			right = mid - 1;
		mid = (left + right) / 2;
	}
	printf("%d\n", mid);
}
int main()
{
	scanf("%d %d", &N, &M);
	vector<int> v(N, 0);
	for (int i = 0; i < N; i++)
		scanf("%d", &v[i]);
	BinSearch(v);
	return 0;
}