[백준 2343] 기타 레슨 (C++)

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

2343번: 기타 레슨

1. 주의할 점

- 이분탐색의 조건을 잘 따져줘야한다(low<=high, low=mid+1, high = mid-1) -> 이 부분때문에 많이 틀렸는데 아직도 많이 헷갈리는 부분이다.

 

2. 구현

- 이분탐색에서 High의 경우 모든 레슨 길이의 합을, Low에는 0을 넣고 시작한다

 

#include <iostream>
#include <algorithm>
using namespace std;
long long result = -1;
int arr[100000];
int num, blue;

bool binarySearch(int val) {
	int cnt = 1;
	long long tot = 0;
	for (int i = 0; i < num; i++) {
		if (arr[i] > val) 
			return false;		
		tot += arr[i];
		if (tot > val) {
			tot = arr[i];
			cnt++;
		}
	}
	if (cnt <= blue) return true;
	else return false;
}

int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);
	long long sum = 0;
	cin >> num >> blue;
	for (int i = 0; i < num; i++) {
		cin >> arr[i];
		sum += arr[i];
	}
	long long low = 0, mid, high = sum;
	while (low <= high) {
		mid = low + (high - low) / 2;
		bool flag = binarySearch(mid);
		if (flag) {
			high = mid - 1;
			result = mid;
		}
		else low = mid + 1;
	}
	cout << result;
	system("pause");
	return 0;
}