용돈 관리

참고한곳

이분탐색 문제이다.

용돈의 최대값을 기준으로 이분탐색을 하는 부분까지 ㅇㅋ.

근데 중간에 Check하는 함수에서 어느 경우에 true, false를 반환해야할 지 몰랐었다.\

문제가 이해가 잘 안되었었음.

문제의 최대범위를 보고 최대값을 잡아도되고

입력에 따라서 최대값을 잡아도 된다.

cpp 코드

#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <math.h>
#include <map>
#include <algorithm>
using namespace std;
#define endl "\n"
#define ll long long

int n, m, a[100005], _max;
ll mx = -1e19;

bool Check(int mid)
{
	int cnt = 1;
	int real_mid = mid;
	for (int i = 0 ; i < n ; ++i)
	{
		if (mid - a[i] >= 0) mid -= a[i];
		else
		{
			mid = real_mid;
			++cnt;
			if (a[i] > mid) return false;
			else mid -= a[i];
		}
	}
	return cnt <= m;
}

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

	cin >> n >> m;
	for (int i = 0; i < n; ++i)
	{
		cin >> a[i];
		mx = (a[i], mx);
	}
	
	ll lo = 1, hi = 10000000004, ret;
	while (lo <= hi)
	{
		int mid = (lo + hi) / 2;
		if (Check(mid))
		{
			hi = mid - 1;
			ret = mid;
		}
		else
			lo = mid + 1;
	}
	cout << ret << endl;
	
	return 0;
}