[백준]Baekjoon1654(이진 탐색)

문제링크 : https://www.acmicpc.net/problem/1654

문제를 읽고나면 전수조사를 통해 해결할 수 있기는 하지만

분명 그런방식으로는 시간초과가 일어나 문제를 해결할 수 없을 것이라는 걸 예측할 수 있다.

그렇게 때문에 사용해준 방식이 이진탐색을 이용한 방식이다.

먼저 최솟값을 1, 최댓값을 랜선 중 가장 큰 수로 놓고 시작하기로 하였다. 또한

예를들어 문제의 예제를 통해 보면

답인 200보다 작을 때는 자른것의 합이 11보다 크거나 같지만 

201이 되는순간 10이 되는것을 알 수 있기 때문에 

이런 특성을 이용해서 이진탐색이 끝날 떄까지 자른것의 합이 n보다 크거나 같은것중

가장 큰 값을 계속 변수에 할당하도록 하였다.

= n) return true;
	else return false;
}
int main()
{
	scanf("%d %d", &k, &n);
	long long max = 0;

	for (int i = 0; i < k; i++) {
		scanf("%lld", &lan[i]);
		if (max < lan[i]) max = lan[i];
	}
	long long left = 1; long long right = max;
	while (left<=right) {
		long long mid = (left + right) / 2;
		if (check(mid)) {
			if (result < mid) {
				result = mid;
			}
			left = mid + 1;
		}
		else {
			right = mid - 1;
		}
	}
	printf("%lld\n", result);
}