[BAE/<JOON> 문제풀이] 1114. 통나무 자르기

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

1114번: 통나무 자르기

서론

파라메트릭 그냥 f, r 외워야할 것 같다. 파라메트릭 풀 때마다 원숭이마냥 이거 브루트포스하고 있는게 너무 한심하다.

첫 자르는 위치도 진짜 쉬운데 못 떠올려서 시간 너무 많이 날림. 근데 풀 때는 조각 길이 로직만 의심하고 첫 자르는 위치는 의심을 못했다.

---

풀이

1. 파라메트릭으로 가장 짧은 긴 조각 길이 구하기

•  현재 mid 값이 될 때까지 조각 길이를 더하다가 넘거나 같아질 때마다 자른다.
• 자른 횟수가 정해진 횟수 c를 넘거나 mid 값보다 현재 조각의 크기가 큰 경우 mid 값으로 자르는 것이 불가능하다.
• 끝까지 자른 경우, 현재 mid 값으로 자르는 것이 가능하다.

 

2. 가장 짧은 최장 조각 길이를 바탕으로 처음 자르는 위치 구하기 

• 조각 길이 배열 순서를 뒤집고 1의 로직을 그대로 적용한다.
• 가장 마지막으로 남은 조각의 길이가 처음 자르는 위치가 된다.

---

코드

#include <bits/stdc++.h>
using namespace std;
bool check(int l, int cc, const vector<int>& arr) {
	int cl = 0;
	int ccc = 0;		
	for (int i = 1; i < arr.size(); i++) {
		if (arr[i] > l) return false;
		if (cl + arr[i] >= l) {			
			if (!(i == arr.size() - 1 && cl + arr[i] == l)) {
				ccc++;
			}
			if (ccc > cc) return false;
			if (cl + arr[i] > l) i--;
			cl = 0;
			continue;
		}
		else {
			cl += arr[i];
		}
	}
	return true;
}
int main() {
	int l, k, c; cin >> l >> k >> c; vector<int> tmp(k + 1), arr(1);
	for (int i = 1; i <= k; i++) {
		cin >> tmp[i];
	}
	sort(tmp.begin() + 1, tmp.end());
	for (int i = 1; i <= k; i++) {
		if (tmp[i] - tmp[i - 1] > 0) {
			arr.push_back(tmp[i] - tmp[i - 1]);
		}
	}
	if (l - tmp[k] > 0) {
		arr.push_back(l - tmp[k]);
	}
	k = arr.size() - 1;
	int f = 0; int r = l; int dap = f; 
	while (f < r) {
		int mid = (f + r) / 2;		
		if (check(mid, c, arr)) {
			dap = mid; // check 가 true 니까 가능한거. 따라서 + 0.
			r = mid;
		}
		else {
			dap = mid + 1; // check 가 false 니까 불가능한거. 따라서 + 1.
			f = mid + 1;
		}
	}
	int cl = 0; vector<int> pl; int cc = 0;
	for (int i = arr.size() - 1; i >= 1; i--) {
		if (cl + arr[i] >= dap) {
			if (!(i == 1 && cl + arr[i] == dap)) {
				cc++;
			}
			if (cl + arr[i] > dap) {
				pl.push_back(cl);
			}
			else {
				pl.push_back(cl + arr[i]);
			}
			if (cl + arr[i] > dap) i++;
			cl = 0;
			continue;
		}
		else {
			cl += arr[i];
		}
	}
	if (cc < c) { // 최적으로 잘라도 자를 수 있는 횟수가 남는 경우
		cout << dap << " " << arr[1];
		return 0;
	}
	if (cl > 0) {
		pl.push_back(cl);	   
	}
	sort(pl.begin(), pl.end());
	int cs = 0;
	for (int i = 1; i <= k; i++) {
		cs += arr[i];
		for (const int& p : pl) {
			if (p == cs) {
				cout << dap << " " << cs;				
				return 0;
			}
		}
	}
	return 0;
}

아래는 코드 정리한거

#include <bits/stdc++.h>
using namespace std;
bool check(int l, int cc, const vector<int>& arr) {
	int cl = 0;
	int ccc = 0;		
	for (int i = 1; i < arr.size(); i++) {
		if (arr[i] > l) return false;
		if (cl + arr[i] >= l) {			
			if (!(i == arr.size() - 1 && cl + arr[i] == l)) {
				ccc++;
			}
			if (ccc > cc) return false;
			if (cl + arr[i] > l) i--;
			cl = 0;
			continue;
		}
		else {
			cl += arr[i];
		}
	}
	return true;
}
int main() {
	int l, k, c; cin >> l >> k >> c; vector<int> tmp(k + 1), arr(1);
	for (int i = 1; i <= k; i++) {
		cin >> tmp[i];
	}
	sort(tmp.begin() + 1, tmp.end());
	for (int i = 1; i <= k; i++) {
		if (tmp[i] - tmp[i - 1] > 0) {
			arr.push_back(tmp[i] - tmp[i - 1]);
		}
	}
	if (l - tmp[k] > 0) {
		arr.push_back(l - tmp[k]);
	}
	k = arr.size() - 1;
	int f = 0; int r = l; int dap = f; 
	while (f < r) {
		int mid = (f + r) / 2;		
		if (check(mid, c, arr)) {
			dap = mid; // check 가 true 니까 가능한거. 따라서 + 0.
			r = mid;
		}
		else {
			dap = mid + 1; // check 가 false 니까 불가능한거. 따라서 + 1.
			f = mid + 1;
		}
	}
	int cl = 0; vector<int> pl; int cc = 0; int fs = arr[1];
	for (int i = arr.size() - 1; i >= 1; i--) {
		if (cl + arr[i] >= dap) {
			if (!(i == 1 && cl + arr[i] == dap)) {
				cc++;
			}
			if (cl + arr[i] > dap) {
				pl.push_back(cl);
				fs = cl;
			}
			else {
				pl.push_back(cl + arr[i]);
				fs = cl + arr[i];
			}
			if (cl + arr[i] > dap) i++;
			cl = 0;
			continue;
		}
		else {
			cl += arr[i];
		}
	}
	if (cc < c) {
		cout << dap << " " << arr[1];
		return 0;
	}
	if (cl > 0) fs = cl;
	cout << dap << " " << fs;
	return 0;
}