[BAE/<JOON> 문제풀이] 24887. 최대한의 휴식

https://www.acmicpc.net/problem/24887

24887번: 최대한의 휴식

서론

파라메트릭 서치 문제. 최솟값의 최댓값이라는 워딩으로 빠르게 알아차릴 수 있었다.

---

풀이

구간의 쉬는 값 k를 이분탐색하면서 전체 배열에 대해 가능한지 여부를 검사한다.

탐색 인자 k 이상 건너뛰면서 주어진 일의 총량을 진행할 수 있는지 여부를 검사한다.

k + 1 칸 이전에서 얻은 최대 일의 총량과 바로 이전 칸에서 얻은 일의 총량을 비교해서 더 큰 값으로 갱신하며

배열의 끝까지 갔을 때 일의 총량이 m을 넘으면 true, m을 넘지못하면 false를 리턴한다.

---

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <cstdlib>
using namespace std;
using ll = unsigned long long;
vector<ll> arr; ll n, m;
bool ch(int k) {
	auto crr = arr;
	for (int i = 2; i <= n; i++) {		
		ll s1 = 0;
		if (i > k + 1) {
			s1 = crr[i - k - 1] + crr[i];
		}
		ll s2 = crr[i - 1];
		ll s3 = s1 > s2 ? s1 : s2;
		crr[i] = crr[i] > s3 ? crr[i] : s3;
		if (crr[i] >= m) return true;
	}
	return false;
}
int main()
{
	ios::sync_with_stdio(0); cin.tie(0); 
	cin >> n >> m; arr = vector<ll>(n + 1);
	ll s = 0;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
		if (arr[i] >= m) {
			cout << "Free!"; return 0;
		}
		s += arr[i];
	}
	if (s < m) {
		cout << -1;	return 0;
	}
	int f = 0; int r = n - 2; int d = 0;
	while (f <= r) {
		int mid = (f + r) / 2;
		if (ch(mid)) {
			f = mid + 1; d = mid;
		}
		else {
			r = mid - 1;
		}
	}
	cout << d;
	return 0;
}