Baekjoon 1654 랜선자르기

Link https://www.acmicpc.net/problem/1654

결과 2148 KB / 4ms

언어 C++ 17

 

풀이

이분탐색을 이용해 정답을 유도하는 과정

초기 범위를 1 ~ 최대값으로 설정하고 최대 랜선 길이를 구하는 함수를 통해 구분을 한다.

기준 값은 현재까지의 최대 값을 기준으로 left와 right를 구분한다.

 

소스코드

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int getMax(vector<int> input) {
	int res = 0;

	for (unsigned int i = 0; i < input.size(); i++)
		if (res < input[i])
			res = input[i];

	return res;
}

long long getMax(long long ll1, long long ll2)
{
	return ll1 < ll2 ? ll2 : ll1;
}

long long getCount(vector<int> input, long long cut) {
	long long res = 0;

	for (unsigned int i = 0; i < input.size(); i++)
		res += (input[i] / cut);

	return res;
}

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

	long long n, tar; cin >> n >> tar;
	vector<int> input(n); for (long long i = 0; i < n; i++) cin >> input[i];

	long long left = 1, right = getMax(input);
	long long res = 0;

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

		if (tar > getCount(input, mid))
			right = mid - 1;
		else {
			left = mid + 1;
			res = getMax(res, mid);
		}
	}

	cout << res;

	return 0;
}