Boj 1114) 통나무 자르기

문제

백준 1114

설명

조건이 두개가 있다. 1. 가장 긴 통나무를 최소로 만들어야한다. 2. 최대 크기만 같다면 처음 자르는 위치가 가장 빨라야한다.

흔한 Parametric Search 풀이처럼 통나무의 최대 크기을 매개변수로 하여 이를 만족하도록 최소한으로 잘라내면 되겠다는 건 쉽게 떠올릴 수 있다. 최소한으로 자른 횟수가 C 를 넘거나 이를 만족하도록 자르는게 불가능한 경우 모두 매개변수를 증가시켜야 되므로 구현도 간단해 보인다. 하지만 문제가 두개 발생한다.

1. 마지막에 자른 위치와 끝위치가 최대 크기를 넘을 수도 있다.
2. 최대 자르는 횟수보다 작게 잘랐다면 더 자를 수도 있다.

이를 간단하게 해결하는 방법은 뒤에서부터 자르는 것이다. 추가로 자르는 위치를 마지막에 자르는 위치라도 해도 되기 때문이다.

이 밖에도 실수할 부분이 꽤 많아서 까다로운 문제였다.

시간 복잡도

O(\(\mathrm{N}\log{\mathrm{N}}\))

코드

using ll = long long;
vector<int> arr;
int C, L, K;
int ans_dist = 1e9 + 10, ans_firstCut = 1e9;

bool Able(int unit)
{
	int pos = L, cnt = 0;
	for (int i = K-1; i >= 0; i--)
	{
		if (pos - arr[i] > unit)
		{
			if (pos - arr[i+1] > unit || arr[i+1] == L)  // 편의상 arr[k-1] 은 항상 L 임
				return false;
			pos = arr[i+1];
			cnt++;
		}
	}
	if (cnt < C) pos = arr[0];    // 더 자를 수 있으면 맨 앞에걸 먼저 자름
	if (pos > unit) return false; // 시작위치와 마지막에 자른 위치의 간격 확인
	if (cnt <= C)
	{
		if (ans_dist > unit) { 
			ans_dist = unit;
			ans_firstCut = pos;   // 최대크기가 바뀌면 무조건 갱신 (실수하기 쉬움)
		}
		else ans_firstCut = min(ans_firstCut, pos);
	}

	return cnt <= C;
}

int main()
{
	cin >> L >> K >> C;
	for (int i = 0; i < K; i++) cin >> arr.emplace_back();
	arr.push_back(L); // 편의상 넣어둠
	sort(arr.begin(), arr.end());
	arr.erase(unique(arr.begin(), arr.end()), arr.end());
	K = arr.size();

	ll s = 1, e = 1e9 + 10;
	while (s <= e)
	{
		ll m = (s + e) / 2;
		if(Able(m))  e = m - 1;
		else         s = m + 1;
	}

	cout << ans_dist << ' ' << ans_firstCut;
}