랜선 자르기 (feat. 백준, 1654번)

랜선 자르기
https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int K, N, count;
	long long start = 1, end = 0, mid, ans = 0;
	int arr[10000];
	cin >> K >> N;
	for (register int k = 0; k < K; ++k)
		cin >> arr[k], end = max(end, (long long)arr[k]);
	mid = (end + start) / 2;
	while ((end - start) >= 0) {
		count = 0;
		for (register int i = 0; i < K; ++i)
			count += arr[i] / mid;
		if (count >= N)
			start = mid + 1, ans = mid;
		else
			end = mid - 1;
		mid = (end + start) / 2;
	}
	cout << ans;
	return 0;
}
// *&)*@*

1. 랜선은 1부터 시작되므로, 1부터 가장 큰 랜선까지에 대해서 이분탐색을 진행합니다.
2. 이분탐색된 mid값 기준으로 랜선을 나눴을때 (잘랐을때) 그 랜선 개수의 총합과 문제로 주어진 N을 서로 비교합니다.
3. 잘린 랜선의 개수의 총합이 문제로 주어진 N보다 크다는 것은 더 큰값의 mid로 랜선을 잘라야 한다는 의미입니다.
4. 따라서 start의 값을 더 크게 하여 mid를 더 크게 해줍니다.