6236번: 용돈 관리

Memo

초기값을 설정하는 것이 중요합니다..!

값이 인출해야하는 금액보다 작아버리면 아예 출금을 못하는 경우가 생기기 때문입니다!

Code

제출 날짜

2021/05/01

메모리

2016 KB

시간

0 ms

#include <iostream>
#include <vector>
#include <algorithm>

int N, M, result, max;
std::vector<int> money;

void output()
{
	std::cout << result;
}

void solution()
{
	auto left = *std::max_element(money.begin(), money.end()), right = max;

	while (left <= right)
	{
		auto mid = (left + right) / 2;
		auto sum = 0, cnt = 1;

		// std::cout << "mid : " << mid << std::endl;
		for(auto& i : money)
		{
			if(sum  + i > mid)
			{
				sum = 0;
				++cnt;
			}
			sum += i;
		}
		if (cnt <= M)
			right = mid - 1;
		else
			left = mid + 1;
	}
	result = left;
}

void input()
{
	std::cin >> N >> M;
	money.resize(N);
	for(auto& i : money)
	{
		std::cin >> i;
		max += i;
	}
}

void preset()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
}

int main()
{
	preset();
	input();
	solution();
	output();
}