[백준] 1114 통나무 자르기 - C++

 

 

 

시간 제한은 2초인데, 입력받는 L의 제한이 10억 까지이다. 

O(L) 시간복잡도로는 해결할 수 없다. 여기서 이분 탐색에 대한 단서를 얻고, 결정 문제로 바꿔서 풀이해야겠다는 전략을 세웠다.

 

구해야 하는 건 조건을 만족할 때의 가장 긴 조각의 길이와 처음 자르게 되는 위치이다.

"가장 긴 조각의 길이" 를 검증 대상으로 설정하고 가장 긴 조각의 길이가 mid일 때 조건을 만족시킬 수 있나? 로 생각하자.

 

이분 탐색을 위해 입력받는 위치를 우선 정렬해 줘야 한다. (위치가 중복되서 나올 수 있어 중복을 제거하는 것도 괜찮을 것 같다)

 

현재 자를 수 있는 위치와 다음 자를 수 있는 위치의 차이를 통해 현재 위치와 다음 위치의 길이를 구할 수 있고, 배열에 값을 저장해 검증에서 사용하자. 

 

처음 자르게 되는 위치는 이분 탐색을 통해 검증할 때 자연스럽게 함께 구할 수 있다.

 

 

#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;

	 
	

}