BOJ 17951 C++

백준 17951 C++ 풀이

문제 접근

이 문제는 조교가 최대한의 점수를 주기위해서 본문에서의 K로 주어지는 시험지를 나눌 그룹의 수 K로 나누어 질때
그룹의 합의 최소가 최대가 되게 이분탐색을 하면된다.

코드

#include <bits/stdc++.h> 

using namespace std;

int solve(const vector<int>& x, int mid)
{
	int size = x.size();
	int po = 0;
	int sum = 0;
	int cnt = 0;
	while (po < size)
	{
		sum += x[po++]; //그룹의 합을 구합니다.
		if (sum >= mid) 
		{
			sum = 0;
			cnt++;
		}
			
	}
	return cnt;
}

int ebun(const vector<int>& x, int k)
{
	int size = x.size();
	int lo = 0;
	int hi = 1e9;
	while (lo <= hi)
	{
		int mid = (lo + hi) / 2;
		if (solve(x, mid) < k)
		{
			hi = mid - 1;
		}
		else
		{
			lo = mid + 1;
		}
	}
	return hi;
}


int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int n, k; cin >> n >> k;
	vector<int> v(n);
	for (int i = 0; i < n; i++)
		cin >> v[i];
	cout << ebun(v, k);
	return 0;
}