[백준] 6236 용돈 관리

백준 6236 용돈 관리

• https://www.acmicpc.net/problem/6236

• 지문을 이해하기 힘들어 원문을 찾아 직접 번역하였다

문제

• http://poj.org/problem?id=3273

Farmer John is an astounding accounting wizard and has realized he might run out of money to run the farm. He has already calculated and recorded the exact amount of money (1 ≤ moneyi ≤ 10,000) that he will need to spend each day over the next N (1 ≤ N ≤ 100,000) days.
FJ wants to create a budget for a sequential set of exactly M (1 ≤ M ≤ N) fiscal periods called "fajomonths". Each of these fajomonths contains a set of 1 or more consecutive days. Every day is contained in exactly one fajomonth.
FJ's goal is to arrange the fajomonths so as to minimize the expenses of the fajomonth with the highest spending and thus determine his monthly spending limit.

• 존은 앞으로 N(1 ≤ N ≤ 100,000)일동안 자신이 하루에 사용할 money(1 ≤ moneyi ≤ 10,000)를 미리 계산해두었다

• 그는 하루 혹은 연이은 날들이 포함된 정확히 M(1 ≤ M ≤ N)개의 회계 기간을 만들고자 한다
  이 회계 기간을 fajomonths라고 부른다
  모든 날들은 단 하나의 fajomonths에 포함된다

• 그는 가장 많이 지출한 fajomonths에서의 지출이 최소가 되도록 fajomonths를 구성하려고 한다
  이때 이 지출의 최솟값을 출력하라

풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, M;
vector<int> money;

//결정 문제: fajomonths에서의 최대 지출이 x일 때 N개의 날들을 M개의 fajomonths로 구성할 수 있는가?  
bool decision(int x) {
	//구성된 fajomonths의 개수
	int cnt = 1;
	int sum = 0;
	for (int i = 0; i < N; ++i) {
		if (sum + money[i] > x) {
			++cnt;
			sum = money[i];
		}
		else sum += money[i];
	}

	if (cnt <= M) return true;
	return false;
}


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

	cin >> N >> M;
	
	int moneySum = 0;
	int moneyMax = 0;
	for (int i = 0; i < N; ++i) {
		int input;
		cin >> input;
		money.push_back(input);

		moneySum += input;
		moneyMax = max(moneyMax, input);
	}

	double lo = moneyMax;
	double hi = moneySum;
	for (int it = 0; it < 100; ++it) {
		double mid = (hi + lo) / 2;

		if (decision(mid)) hi = mid;
		else lo = mid;
	}

	cout << (int)hi;
	return 0;
}