[백준 C++] 1654 랜선 자르기 - 이분탐색

1654번: 랜선 자르기

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

vector<int> Lines;

int main()
{
	int K, N;
	cin >> K >> N;

	Lines.reserve(K);
	for (int i = 0; i < K; ++i)
	{
		int Line;
		cin >> Line;
		Lines.emplace_back(Line);
	}

	int Result = 0;
	long long Length = 0;
	long long MinLength = 1;
	long long MaxLength = *max_element(Lines.begin(), Lines.end());
	while (MinLength <= MaxLength)
	{
		Length = (MinLength + MaxLength) / 2;

		int Count = 0;
		for (const int& Line : Lines)
		{
			Count += Line / Length;
		}

		if (Count < N)
		{
			MaxLength = Length - 1;
		}
		else
		{
			Result = Length;
			MinLength = Length + 1;
		}
	}

	cout << Result;
}

---

 

이전에 풀이한 2805(나무 자르기) 문제와 풀이방식이 거의 유사합니다.

 

이번 문제에서는 랜선의 길이가 INT_MAX값까지 가능하므로

길이 탐색을 위한 변수의 자료형 선택에 주의가 필요합니다.