백준 - 1654번 랜선 자르기

문제

랜선 길이들이 주어질 때 길이가 같은 n개 이상의 랜선으로 자르고 싶다!
만들 수 있는 최대 랜선의 길이는?

생각

직접 이 길이로도 잘라보고 저 길이로도 잘라보며
최대 랜선의 길이를 구해야 하는데,
해봐야하는 랜선 길이의 범위가 엄청 크니까 이분탐색 문제!~

왼쪽편 오른쪽 편 범위 정하고 가운데 값 변경해보며
가능하면 더 큰 쪽 가보고
불 가능하면 더 작은쪽 가보고
이분탐색 구조만 알면 쉬운 문제~!!

주의해야할 점은 최소 자르는 길이가 0이 아니라 1이라는 점
길이 0으로 랜선 못 나눔!~~!

코드

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <utility>

using namespace std;

int k, n;
long long input[10005], result, maxLen;

bool solve(long long tempLen) {
	//tempLen으로 잘랐을 때 n개를 만들 수 있는지 없는지 반환
	int count = 0;
	for (int i = 0; i < k; i++) {
		count += input[i] / tempLen;
	}
	if (count < n) {
		return false;
	}
	else {
		return true;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> k >> n;

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

	long long l = 1; //0이 아니라 1인 것에 주의
	long long r = maxLen; //받은거 중에 제일 긴 거 보다 긴 값은 안되겠구만!

	long long m = 0;

	while (l <= r) {
		m = (l + r) / 2;
		
		if (solve(m)) {
			l = m + 1;
			result = m;
		}
		else {
			r = m - 1;
		}
	}

	cout << result;

	return 0;
}