BOJ 6236 | 용돈 관리

Parametric Search를 이용해 푸는 문제이다.

딱히 주의할 점은 없다.
money의 모든 원소가 K보다는 작아야 한다는 정도?

#include <bits/stdc++.h>
using namespace std;

int N, M;
vector<int> money;

bool check(int K){
	int cnt = 0;
	int current = 0;
	for (auto i : money){
		
		if (i > K) return false;
		
		if (current < i){
			cnt++;
			current = K;
		}
		
		current -= i;
	}
	
	if (cnt <= M) return true;
	else return false;
}

int main(){
	cin >> N >> M;
	for (int i = 0; i < N; i++){
		int t; cin >> t;
		money.push_back(t);
	}
	
	int lo = 0;
	int hi = 1e9;
	
	while (lo + 1 < hi){
		int mid = (lo+hi)/2;
		if (check(mid)) hi = mid;
		else lo = mid;
		
	}
	
	cout << hi;
	
}