백준 1654 랜선 자르기

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 k개의 랜선을 보유하고 있을 때 랜선을 잘라 N개의 개수의 랜선을 만들 때 모두 동일한 길이로 만드는데 가장 길게 할 수 있는 길이를 구하는 문제입니다. 주어진 k개 10000까지 가능하고 N이 10000000 까지 가능하므로 어떤값으로 모든 k를 나눠서 그합을 더했을 때 N이 되는지 일일이 확인한다면 시간이 많이 걸리게 될것입니다.

 

따라서 이분탐색을 이용하여 가장큰 값을 찾아내면 됩니다. 주의할 점은 랜선의 길이가 2^31-1까지 가능한데 중간에 두 랜선 사이의 연산이 있을 수 있어서 오버플로우 가능성이 있는 변수들은 long long으로 선언을 해주어야 합니다.

 

다음은 코드입니다.

 

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

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int N,K;
	cin >> K >> N;
	int arr[K];
	int result;
	long long max = 0;
	long long left = 0;
	long long right = pow(2, 31) - 1;
	long long mid;
	for(int i = 0; i < K; i++) {
		cin >> arr[i];
	}
	
	while(left <= right) {
		mid = (left+right)/2;
		result = 0;
		for(int j = 0; j < K; j++)
				result = result + arr[j] / mid;
			
			if(result >= N) {
				left = mid+1;
				if(mid > max)
					max = mid;
				}			
			else if(result < N){
				right = mid-1;
		}
	}
	cout<<max;
	
	return 0;
}