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

[백준 6236번 / C++] 용돈 관리

 위의 문제와 거의 똑같은 문제다. 해당 링크 설명을 보고 한번 풀어보자.

#include <iostream>
#include <climits>
#include <vector>
using namespace std;
int l = 1; int h = INT_MAX; 
int n, m; 
vector <int> v; 
bool check(int mid) {
	for (int i = 0; i < n; i++) {
		if (v[i] > mid)return 0; 
	}
	int sum = 0; 
	int cnt = 1; 
	for (int i = 0; i < n; i++) {
		if (sum+v[i] <= mid) {
			sum+=v[i]; 
		}
		else {
			sum = 0; 
			cnt++; 
			sum += v[i]; 
		}
	}
	return cnt <= m; 
}

int main() {
	cin >> n >> m; 
	for (int i = 0; i < n; i++) {
		int a; cin >> a; 
		v.push_back(a); 
	}
	int result = 0; 
	while (l <= h) {
		int mid = (l + h) / 2; 		
		if (check(mid)) {
			h = mid - 1; 
			result = mid;
		}
		else {
			l = mid + 1; 
		}

	}
	cout << result; 

}

2343번: 기타 레슨