기타레슨

어떤것을 최소화, 최대화라는 것은,

이 값으로 될까 안될까? 를 따진다음에 lo, hi를 통해서 mid를 만들어서 mid를 중심으로 왔다리 갓다리 하면서

=> 결정문제로 만드는 것이다.

그래서 이 mid값을 기준으로 레코드판을 채워서 값을 내는 것임.

mid가 27이라는 숫자부터 시작을 해서 Check()함수에다가 mid를 넣어줌.

그러면 일단 for문에서 arr[i] > mid인것은 말이 안되니까 다 넘기고

temp에다가 mid넣고

이런식으로 mid - arr[i]는 빨간 칸을 채워가는 것이다. 그러다가 삐져 나가면은 mid = temp로 다시 만들고 ++cnt해준다.

기억하자 LIS 이분탐색문제는 결정문제로 만들어보리자.

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, arr[100004], ret = 0;
ll sum = 0;
ll l, r, hi, lo;

bool Check(int mid)
{
	for (int i = 0; i < n; ++i)
	{
		if (arr[i] > mid)
		{
			return false;
		}
	}
	int temp = mid;
	int cnt = 0;
	for (int i = 0; i < n; ++i)
	{
		if (mid - arr[i] < 0)
		{
			mid = temp;
			++cnt;
		}
		mid -= arr[i];
	}
	if (mid != temp) ++cnt;
	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 >> arr[i];
		sum += arr[i];
	}
	
	lo = 0; hi = sum;
	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;
}