백준 2343번 [기타 레슨]

이진 탐색, 매개 변수 탐색

이진 탐색의 start, end, mid을 배열의 값에만 국한시키지 말고 문제와 관련된 매개 변수로 해본다.

ㅡ> 정렬된 배열이 아니더라도 이진 탐색 사용 가능

N, M <= 100,000이므로 O(logn)의 알고리즘 이진 탐색 생각

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

	int n, m;
	cin >> n >> m;
	vector<int> v;
	int end = 0;
	int start = 0;

	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		v.push_back(x);
		end += x;
		start = max(start, x);
	}

	while (start <= end) {
		int mid = (start + end) / 2;
		int sum = 0;
		int count = 1;

		for (int i = 0; i < n; i++) {
			if (sum + v[i] > mid) {
				count++;
				sum = 0;
			}
			sum += v[i];
		}
		if (count > m) start = mid + 1;
		else end = mid - 1;
	}
	cout << start;

	return 0;
}