백준 1654 랜선 자르기

c언어 문풀

랜선 자르기

 

캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다.

이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다!

이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.

 

 

랜선의 개수가 10000 까지고 길이는 1000000이므로 반복문으로 풀면 시간초과에 걸려 이진 탐색을 해주어야 한다

.

이진 탐색 함수를 따로 만들어 주었다. 

입력을 받으면서 제일 긴 전선의 길이를 따로 저장해주었다.

이진 탐색 함수에서 파라미터를 (1,최대 전선길이)로 주어 zero division 에러가 나지 않도록 해주었다.

mid값을 찾아가면서 만약 s값이 e 보다 클 경우 e를 return 해줘 종료조건을 설정해줬다. 

 

mid 의 가능 범위는 1 부터 최대 전선의 길이임

 

total로 나눠진 숫자의 합을 구해 랜선의 개수를 세주고 그 수가 k보다 크거나 같으면 (mid+1, e)로 이진 탐색을 호출해줘 더 큰 길이 범위에서 가능한 개수를 찾아주었고  작은 경우에는 (s,mid-1)로 호출해줘 더 작은 길이 범위에서 탐색하도록 하였다. (s가 더 커졌다는 의미는 앞선 s와 e가 같은 숫자이면서 total이 k보다 크거나 같았다는 의미이므로 정답임)

 

#include<stdio.h>
long long int arr[10000] = { 0, };
int n, k;

long long bin_search(long long s, long long e) {
	if (s > e) {
		return e;
	}
	long long mid = (s + e) / 2;
	long long total = 0;

	for (int i = 0; i < n; i++) {
		total += arr[i] / mid;
	}

	if (total >= k) {
		return bin_search(mid + 1, e);
	}
	else {
		return bin_search(s, mid - 1);
	}
}

int main(){
	scanf("%d %d", &n, &k);
	long long high = 0;
	for (int i = 0; i < n; i++) {
		scanf("%lld", &arr[i]);
		if (arr[i] > high) {
			high = arr[i];
		}
	}
	long long line =bin_search(1, high);
	printf("%lld", line);
	return 0;
}