(백준) 1114 Log Cutting – C++

제한 시간은 2초이고 입력 L의 제한은 최대 10억입니다.

O(L) 시간 복잡도로 풀 수 없습니다. 여기서는 bipartite search에 대한 단서를 얻고 이를 Decision problem으로 전환하여 해결하는 전략을 세웠다.

당신이 찾아야 할 것은 조건이 충족되었을 때입니다. 가장 긴 조각의 길이그리고 어디를 먼저 자를까오전.

“가장 긴 조각의 길이“를 검증 대상으로 설정하고 가장 긴 조각의 길이가 중간일 때 조건을 만족할 수 있습니까?

이분 검색의 경우 입력 위치를 먼저 정렬해야 합니다. (위치가 중복될 수 있으니 중복 제거해도 괜찮습니다.)

현재 절단 가능한 위치와 다음 절단 가능한 위치의 차이를 통해 현재 위치와 다음 위치의 길이를 구할 수 있으며, 그 값을 배열에 저장하여 검증에 사용할 수 있습니다.

처음 잘리는 위치는 bipartite search를 통해 확인할 때 자연스럽게 함께 얻을 수 있습니다.

#include <bits/stdc++.h>
#define endl "\n"
#define INF 987654321;
#define INF2 1000000001;

typedef long long ll;
using namespace std;

int l, k, c;
vector<int> v;
vector<int> len;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> l >> k >> c;

	v.resize(k+1);
	len.resize(k+1);

	for(int i=0; i<k; i++) cin >> v(i);
	v(k) = l;

	sort(v.begin(), v.end());

	len(0) = v(0);

	for(int i=1; i<k+1; i++) len(i) = v(i) - v(i-1);

	int left = 0;
	int right = 1000000000;

	int ans1 = -1;
	int ans2 = -1;


	while(left <= right) {
		int mid = (left + right) / 2;

		int cut = 0;
		int idx = 0;
		int start = 0;
		
		for(int i=k; i>=0; i--) {
			if(len(i) > mid) {
				cut = INF;
				break;
			}

			if(start + len(i) > mid) {
				start = 0;
				cut++;
				idx = i;
			}

			start += len(i);
		}

		if(cut > c) {
			left = mid + 1;
		} else {
			right = mid - 1;
			ans1 = mid;
			ans2 = (cut == c) ? v(idx) : v(0);
		}
	}

	cout << ans1 << " " << ans2 << endl;

	 
	

}