[C++] 백준 2343번: 기타 레슨

www.acmicpc.net/problem/2343

2343번: 기타 레슨

처음엔 정렬되지 않은 벡터를 이분탐색을 어떻게 진행하지 고민했었던 문제이다. 예전에 L사 코테를 봤을 때 나왔던 문제랑 매우 유사해서 꼭 풀어보고 싶었다!

 

다소 좀 생소한 이분 탐색 유형인 것 같아 고민을 좀 했었는데 반례 모음을 보고 풀 수 있었다.

 

이분 탐색을 진행할때 left와 right의 초기 값에도 신경을 써야된다는 것을 알 수 있었다.

 

참고한 반례모음: bingorithm.tistory.com/10

"백준 2343번-기타 레슨" 반례 모음

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;

int n, m;
long long sum[100001];

int main() {
	int x;
	vector<int> v;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> x;
		v.push_back(x);
	}
	int left = *max_element(v.begin(), v.end());
	int right = 10000 * n;

	while (left <= right) {
		int c = 1;
		int mid = (left + right) / 2;
		for (int i = 0; i < v.size(); i++) {
			sum[c] += v[i];
			if (sum[c] > mid) {
				sum[c] -= v[i];
				c++;
				sum[c] += v[i];
			}
		}
		if (c > m) {
			left = mid + 1;
		}
		else {
			right = mid - 1;
		}
		for (int i = 1; i <= m; i++) {
			sum[i] = 0;
		}
	}
	cout << left;
	return 0;
}