언제나 처음처럼

[문제 링크]

분할정복과 이분탐색이 섞인 문제인거같다. 이분탐색 풀이법이 생각나지 않아 다른사람들의 풀이법을 참고하였다. 3일 후에 다시한번 풀어봐야 겠다.

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

vector<int> dayMoney;
int N, M, sum;

bool Solution(int money)
{
	int temp = money, withdraw = 1;
	for (int i = 0; i < N; i++)
	{
		if (dayMoney[i] > money)
			return false;
		if (temp - dayMoney[i] < 0)
		{
			temp = money;
			withdraw++;
		}
		temp -= dayMoney[i];
	}
	return M >= withdraw;
}
int main(void)
{
	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		int n;
		cin >> n;
		dayMoney.push_back(n);
		sum += n;
	}

	// binary_search //
	int start = 1, end = sum; // sum은 M이 1인 모든 금액을 더한 값
	int result;
	while (start <= end)
	{
		int mid = (start + end) / 2;
		if (Solution(mid))	// 인출횟수가 M보다 작거나 같음 -> 인출금을 줄여보자
		{
			result = mid;
			end = mid -1;
		}
		else
			start = mid + 1;
	}
	cout << result << endl;
	return 0;
}

알고리즘 200일 프로젝트 - 39day