[BAE/<JOON> 문제풀이] 17179. 케이크 자르기

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

17179번: 케이크 자르기

 

서론

무슨 문젠지 모르겠어서 태그 봤는데 파라메트릭이 또,,

앞으로 문제가 DP 같은데 입력값이 좀 이상하다 싶으면 파라메트릭으로 가야겠다. 이건 판정 방법을 모르겠음. 문제를 많이 안풀어서 그런가. 내일은 통나무 풀어봐야겠다. 이 문제 보니까 그건 이중 파라메트릭 같음.

---

아이디어

케익을 자르는 구간 고민하지 말고 다 잘라놓은 다음에 합치기

합치면서 최소 길이만 검사하고 마지막까지 합쳤을 때 조각 갯수가 정해진 횟수 이상이 되면 그 길이가 구하는 길이다.

---

풀이

• 자르는 횟수 + 1 = 조각 개수
• 케익 순서를 바꿀 수는 없으므로 그냥 순차적으로 더해가며 정해진 길이를 넘는 횟수를 구하면 된다.
• 파라메트릭 서치를 통해 최종적으로 구해지는 값은 정해진 갯수를 만들지 못하는 최소 길이 이므로 답은 파라메트릭 서치 결과 - 1이다.

---

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
using ull = unsigned long long;
bool check(int msz, int cc, const vector<int>& arr) {
	int cp = 0;
	int ccc = 0;
	for (int i = 1; i < arr.size(); i++) {
		if (cp + arr[i] >= msz) {
			cp = 0;
			ccc++;
			if (ccc >= cc) return true;
		}
		else cp += arr[i]; 
	}
	return false;
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, m, l; cin >> n >> m >> l; vector<int> cp(m + 2), arr(n + 1); 
	int prev = 0;
	for (int i = 1; i <= m; i++) {
		int t; cin >> t;
		cp[i] = t - prev;		
		prev = t;
	}
	cp[m + 1] = l - prev; m++;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
		arr[i]++;
	}	
	for (int i = 1; i <= n; i++) {
		int f = 1; int r = l / arr[i];
		while (f <= r) {
			int mid = (f + r) / 2;
			if (check(mid, arr[i], cp)) {
				f = mid + 1;
			}
			else {
				r = mid - 1;
			}
		}
		cout << f - 1 << "\n";
	}	
	return 0;
}