ShaShaKa Dev Note

나무 자르기

08 September 2019

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

이번은 이분 탐색을 응용하여 최솟값이나 최댓값을 찾는 문제를 풀어보도록 하겠습니다.

#include<stdio.h>

static int N;
static long long target;
static long long *arr;
static long long max = 0;

long long binarySearch();

int main(void) {
	
	scanf("%d %lld", &N, &target);

	arr = new long long[N];

	for (int i = 0; i < N; i++)
	{
		scanf("%lld", &arr[i]);
		if (arr[i] > max)
		{
			max = arr[i];
		}
	}

	printf("%lld", binarySearch());
	
	return 0;
}

bool isAvailable(long long val) {
	long long sum = 0;
	for (int i = 0; i < N; i++)
	{
		long long rest =  arr[i] - val;
		if (rest > 0)
		{
			sum += rest;
		}
	}

	return sum >= target;
}

long long binarySearch() {
	long long start = 0;
	long long end = max;

	while (end >= start)
	{
		long long mid = (start + end) / 2;

		if (end - start <=1)
		{
			if (isAvailable(end)) {
				return end;
			}
			return start;
		}

		if (isAvailable(mid))
		{
			start = mid;
		}
		else {
			end = mid - 1;
		}
	}
	
	return 0;
}

나무를 잘라서 남는 합이 원하는 나무의 총길이보다 크거나 같을 때의 값을 구하는 문제입니다.
만약 나무를 자르는 높이보다 나무의 길이가 작아도 음수를 더하지는 않으므로, 해당 경우는 제외하도록 합니다.
0부터 최대 높이까지의 범위로 이분 탐색을 진행하여, end-start <=1 인 경우에 해당하는 값 중 큰 값을 return 해주도록 합니다.