ShaShaKa Dev Note

랜선 자르기

08 September 2019

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

이번은 흔히 parametric search라고도 부르는, 이분 탐색을 응용하여 최솟값이나 최댓값을 찾는 테크닉을 배우는 문제를 풀어보도록 하겠습니다.

#include<stdio.h>

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

long long binarySearch();

int main(void) {

	scanf("%d %d", &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(int val) {
	int sum = 0;
	for (int i = 0; i < N; i++)
	{
		sum += arr[i] / val;
	}

	if (sum >= target)
	{
		return true;
	}
	return false;
}

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이고, 가장 큰 길이는 가지고 있는 랜선의 길이의 최대값입니다.
여기서 최소값과 최대값 사이에서 이분 탐색을 통해, 주어진 조건을 만족하는, 즉 잘라서 해당 갯수가 나오는 값을 찾으면 됩니다.
해당 갯수가 나오면 해당 값을 start로 정하고, 안 나오면 end를 mid-1로 정하여 점점 범위를 줄여주고
start와 end의 차가 1일때, end와 start 값을 비교하여 가능한 것 중 큰 값을 return해주도록 합니다.