[백준 C++] 1654 : 랜선 자르기

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

이분탐색을 응용하는 문제이다.

N의 개수와 맞는 최대 길이를 구해야 하는데, 가능한 범위 (1 ~ 랜선 최대 길이)에서 확인해가면서 값을 찾아야 한다.

---

#include <iostream>
#include <vector>

using namespace std;

vector<int> list;
int N;

int calculate(unsigned int start, unsigned int end, int ans)
{
	if (start > end)
		return ans;

	unsigned int len = (start + end) / 2;
	int count = 0;

	for (int i = 0; i < list.size(); i++)
		count += list.at(i) / len;

	if (count >= N)
		return calculate(len + 1, end, ans > len ? ans : len);
	else
		return calculate(start, len - 1, ans);
}

int main()
{
	int K, max = 0;
	cin >> K >> N;

	for (int i = 0; i < K; i++)
	{
		int temp;
		cin >> temp;
		
		if (max < temp)
			max = temp;

		list.push_back(temp);
	}

	cout << calculate(1, max, 0) << endl;

	return 0;
}

코드를 간단하게 설명하자면 다음과 같다.

 

list에 랜선들을 넣으면서 최대 길이를 확인하여 범위를 정한다.

calculate를 반복해가면서 가능한 길이를 확인하는데, count의 개수가 구해야 하는 개수 N보다 크거나 같으면 정답이거나 길이가 작은 것이기 때문에 현재 len보다 큰 값을 확인해보는 것이고, 반대의 경우는 현재 len값보다 작은 값을 확인하는 것이다.

count >= N일 때 같은 count여도 정답값보다 길이가 짧을 수 있기 때문에 이전 과정에서 얻은 ans값과 현재 len값을 비교해서 최댓값을 넣어주었다.

 

이 코드에서 조심해야 할 점은 모든 길이 자체는 int 범위를 초과하지 않지만, 구하는 과정에서 초과할 가능성이 있기 때문에 long long 또는 unsigned를 통해 초과하지 않게 해주어야 한다.

또한 길이 범위는 1부터 시작한다는 것도 생각해야 할 것이다.