[C++] 백준 1654번 - 랜선 자르기(retry needed)

처음으로 이분 탐색을 써본 문제.

이분 탐색을 처음 써보는 거라 많이 어색하기도 하고,

구현을 어떻게 해야하는지 감이 잘 안와서

여러 블로그를 보고 조금 터득했다.

이분 탐색 문제를 더 풀어봐야 감이 올 것 같다.

이 문제도 내 힘으로 푼 것이 아니라 나중에 한번 더 풀어봐야겠다.

 

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

#define MAX 10000

int n, m;
long long int line_arr[MAX];

bool isPossible(long long line) {
	int count = 0;
	for (int i = 0; i < n; i++) {
		count += line_arr[i] / line;
	}

	if (count >= m)
		return true;
	return false;
}

int main() {

	ios::sync_with_stdio(false);
	cin.tie(0);


	cin >> n >> m;

	long long high = 0, low = 1, answer = 0;

	for (int i = 0; i < n; i++) {
		cin >> line_arr[i];

		high = max(high, line_arr[i]);
	}

	while (low <= high) {
		long long mid = (high + low) / 2;

		if (isPossible(mid)) {
			if (answer < mid) {
				answer = mid;
			}
			low = mid + 1;
		}
		else {
			high = mid - 1;
		}
	}

	cout << answer << '\n';

	return 0;
}