[백준][1654][c++] 랜선 자르기

랜선자르기 문제 링크

[문제 풀이]
랜선의 길이가 k_l = 2^(31)-1임으로 완전탐색으로 풀시 시간초과할 것임으로 이분탐색으로 풀어야 한다. 그렇게 되면 k*log(k_l)이 될 것이다.
전형적인 이분탐색 문제이다.
주의할 점
1) "N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다."라는 말이 있으니 조건에 반영해야한다
2) 랜선의 길이가 2^(31)-1보다 작거나 같은 자연수이기에 long long 자료형 사용해야 한다

[코드]

#include <iostream>
#include <vector>
#include <algorithm>
#define K_MAX 10001

using namespace std;

int K, N;
vector<long long> arr;
vector<int> result;


int calculate_number(long long criteria, vector<long long>& numbers) {
	long long result = 0;
	for (int i = 0; i < numbers.size(); i++) {
		result += numbers[i] / criteria;
	}
	return result;
}


long long solve(long long last_value, long long summed_value) {
	long long max_value = -1;
	long long left = 1;
	//int mid = summed_value / N;	
	long long right = last_value;
	long long mid = (left + right) / 2;

	while (1) {
		long long num = calculate_number(mid, arr);
		
		if (num < N) {
			right = mid;
			mid = (right + left) / 2;
		}
		else if (num >= N) {
			if (max_value < mid) max_value = mid;
			if (left > right) break;
			left = mid;
			mid = (right + left) / 2;
		}

		
	}

	return max_value;
}


int main() {
	cin >> K >> N;
	long long value;
	long long m_value = -1;
	long long sum_value = 0;
	for (int k = 0; k < K; k++) {
		cin >> value;
		sum_value += value;
		if (m_value < value) m_value = value;
		arr.push_back(value);
	}
	long long ans = solve(m_value, sum_value);
	cout << ans << "\n";
}

[총평]
이분탐색 알고리즘만 정확히 알고 있으면 쉽게 풀 수 있는 문제...였다.