백준 랜선 자르기 1654 C++

k개의 랜선으로 n개의 랜선을 만들 때, 최대 길이를 구하는 문제.

1부터 주어진 최대 길이의 랜선 사이의 길이를 고르면 된다.

1과 최대 길이값의 중간 길이부터 시작한다.

랜선을 잘랐을 때,

1. n보다 많거나 같은 개수가 만들어진다면
   • 현재 길이보다 길게 잘라도 된다.
   • 최소값을 중간값+1로 증가시켜 중간 길이를 늘린다.
   • 현재 길이가 최대 길이일 수 있으므로 length 변수와 비교하여 큰 값을 length에 저장한다.
2. n보다 적은 개수가 만들어진다면
   • 현재 길이보다 짧게 잘라야한다.
   • 최대값을 중간값-1로 감소시켜 중간 길이를 줄인다.

위 과정을 반복하면서 최소값과 최대값을 계속 늘이고 줄이다보면, 최소값이 최대값보다 커지는 경우가 발생한다.

그 때, length에 저장된 값이 가능한 가장 긴 길이이다.

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

unsigned int n, k, length;
unsigned int len[10000];

int main() {
	cin >> k >> n;

	unsigned int left = 1;
	unsigned int right = 0;
	unsigned int mid;

	for (int i = 0; i < k; i++) {
		cin >> len[i];
		right = max(right, len[i]);
	}

	while (left <= right) {
		mid = (left + right) / 2;

		int cnt = 0;
		for (int i = 0; i < k; i++) {
			cnt += len[i] / mid;
		}
		if (cnt < n) {
			right = mid - 1;
		}
		else {
			left = mid + 1;
			length = max(length, mid);
		}
	}

	cout << length;
}

주어진 길이들만을 이용하여 푸려면 어렵지만, 최대값을 추출해서 1과 비교하면 쉽게 풀 수 있다.