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

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

1654번: 랜선 자르기

---

 문제 풀이

N개의 랜선을 만드는데 그 길이를 최대로 만들어야 한다.

브루트 포스로 풀 수 있지만 무조건 시간 초과가 발생한다.

이진 탐색으로 탐색 횟수를 줄여야 한다.

 

가장 긴 길이와 가장 짧은 길이(1) 사이에 답이 존재한다.

이분 탐색을 통해서 그 중간 값과 비교할 텐데

잘랐을 경우 N개가 되는 값이 여러 개 존재한다.

그중에서 최댓값을 찾아야 해서 잘랐을 때 N개 이상이라면 랜선의 길이를 1씩 늘려나가면서 비교한다.

 느낀 점

그렇게 어려운 문제는 아니었다. 처음에 STL 컨테이너 set으로 구현하려고 했는데 중복된 값에 대해서 문제가 생긴다! 그래서 그냥 배열로 풀었다.

 코드

#include <iostream>
#include <algorithm>

using namespace std;

int n, k;
long long num[10001];

long long binary(long long left, long long right) {
	long long result = 0;
	while (left <= right) {
		long long mid = (left + right) / 2;
		int cnt = 0;
		for (int i = 0; i < k; i++) {
			cnt += num[i] / mid;
		}
		if (cnt >= n) {
			if (result < mid) result = mid;
			left = mid + 1;
		}
		else right = mid - 1;
	}
	return result;
}

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

	cin >> k >> n;
	for (int i = 0; i < k;i++) {
		cin >> num[i];
	}
	sort(num, num + k);

	cout << binary(1, num[k - 1]);
}