[BOJ]1654번: 랜선 자르기 (c++)

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

1654번: 랜선 자르기

 

이분탐색

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int count_possible_line(vector<int> &lines, long long len)
{
	int cnt = 0;
	for (int i = 0; i < lines.size(); ++i)
	{
		cnt += lines[i] / len;
	}
	return cnt;
}

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

	// 입력
	int K, N;
	cin >> K >> N;
	vector<int> lines(K);
	for (int i = 0; i < K; ++i)
	{
		cin >> lines[i];
	}

	// 이분탐색
	long long answer = 0;
	long long left = 1;
	long long right = *max_element(lines.begin(), lines.end());

	while (left <= right)
	{
		long long mid = (left + right) / 2;
		int cnt = count_possible_line(lines, mid);

		// 개수가 N이상이면 더 크게 자를수 있는지 확인해야 함
		if (cnt >= N)
		{
			// 자르는 크기 최대값 갱신
			answer = max(mid, answer);
			left = mid + 1;
		}
		else
		{
			right = mid - 1;
		}
	}

	// 출력
	cout << answer;

	return 0;
}

 

 

랜선의 길이는 2^31 - 1보다 작거나 같은 자연수이다.

 

이분탐색으로 조건을 만족하는 수를 찾는 문제인데, 자료형의 크기를 주의해야 한다

mid = (left + right) / 2  중간값을 찾을 때 int형의 범위를 넘을 수 있기 때문에

long long형을 써야 한다.