[BOJ] 백준 1654번: 랜선 자르기, 이분 탐색 (Binary Search)

www.acmicpc.net/problem/1654

1654번: 랜선 자르기

이 문제는 주어진 랜선 K개의 길이를 잘라 같은 길이의 N개를 만들 때 최대 랜선의 길이를 구하는 문제입니다.

랜선의 길이가 INT_MAX 값보다 작거나 같은 자연수 이므로 Naive한 방법으로는 시간초과가 발생하므로 해결할 수 없습니다.

자를 수 있는 랜선 길이의 범위 내에서 가능한 최대 길이를 구하는 문제로 정렬된 순열에서 특정 값을 찾는 문제로 해석할 수 있고 이는 이분 탐색을 사용하면 O(KlgINT_MAX) 시간복잡도로 해결 할 수 있습니다. (현재 시도해볼 값 mid로 K개를 나눴을때 몫이 N개 이상인지 아닌지로 양 끝값을 조절하므로.)

#include <iostream>
#include <algorithm>
#include <vector>
#include <memory.h>
#include <deque>

using namespace std;
typedef long long ll;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	ll k, n, arr[10001];
	cin >> k >> n;
	for (ll i = 0; i < k; i++) {
		cin >> arr[i];
	}
	ll s = 1, e = 3e9;
	ll mid;
	ll ans = 0;
	while(s<=e){
		mid = (s + e) / 2;
		ll cnt = 0;
		for (ll i = 0; i < k; i++) {
			cnt += (arr[i] / mid);
		}
		if (cnt >= n) {
			ans = max(ans,mid);
			s = mid + 1;
		}
		else {
			e = mid - 1;
		}
	}
	cout << ans;
}

 

유사한 문제로 2805번: 나무 자르기 가 있습니다.