BOJ 1114 통나무 자르기

이 문제의 핵심은 모든 통나무 조각 길이보다 큰 경우를 만족하는 적절한 길이의 통나무를 구하는 문제이다.

예를들어 L =9, K=2, C=1 일 경우 나올수 있는 통나무 조각은 4,1,4이다. 이때 모든 통나무 조각 길이 보다 긴 적절한 길이의 통나무를 구해야한다.

 

우리가 생각해야하는 조건은 두가지이다.

1. 모든 잘린 통나무 조각은 적절히 자를수 있는 최대 길이(mid)로 모두 자를 수 있어야 한다.

2. 자를수 있는 횟수를 초과 하면 안된다.

 

이를 바탕으로 풀이를 다음과 같이 생각해볼 수 있다.

1. 만약 잘린 통나무 누적 길이가 mid보다 커지는 순간까지 cut을 하지 않고, 커지는 순간 cnt을 증가시켜준다.

2. 이후 마지막으로 누적한 통나무의 길이가 mid 보다 클경우 위의 조건 1을 만족하지 않아 mid를 증가시켜 이분탐색을 수행한다.

3. 1번을 반복한면서 모든 통나무 조각을 순회하고난 다음 cnt가 cut 보다 클경우 자를수 있는 횟수를 초과하였기 때문에 mid를 증가시켜 조정해준다.

 

이분탐색 mid조정 과정에서 mid의 길이가 최소가 되게 해야하므로 최소값을 저장시켜준다. 이렇게 구한 최소 길이를 가지고 cut 횟수에 맞게 나무를 뒤에서 부터 잘라준다.

 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int l, c, k;
int maxLength = (int)2e9;
vector<int> v;

//아이디어는 적절한 길이 mid를 이분탐색을 통해 찾아간다. 여기서 정답은 적절하게 자른 통나무 각각의 길이가
//mid의 길이보다 작아야한다. 
void BS(int left, int right)
{
	if(left > right)
	{
		return;
	}
	int mid = (left + right) / 2;
	int length = l;
	int cnt = 0;

	int diff = 0;
	//통나무를 잘라야할 경우는 구간의 길이가 mid보다 커졌을때이다.
	for(int i = k; i >=0; i--)
	{
		diff += (v[i+1] - v[i]);
		if(diff > mid)//누적합이 mid보다 긴경우 v[i]에서 자른다.
		{
			cnt++;
			diff = v[i+1] - v[i]; //마지막에 추가한 길이가
			if(diff > mid) //마지막에 추가한 길이가 mid보다 길경우 mid를 재조정해야한다.
			{
				cnt = c + 1;
				break;
			}
		}
	}

	if(cnt > c)//모든 통나무를 mid의 길이로 자를수 없기때문에 mid를 늘려준다.
	{
		return BS(mid+1, right);
	}
	else
	{
		maxLength = min(maxLength, mid);
		return BS(left, mid-1);
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> l >> k >> c;

	v.push_back(0);
	v.push_back(l);

	for(int i = 0; i < k; i++)
	{
		int num;
		cin >> num;
		v.push_back(num);
	}

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

	int start = 0;
	int end = (int)1e9+1;

	BS(0,l);

	int diff = 0, cnt = 0;
	int idx = k;

	for(int i = k; i >= 0; i--)
	{
		diff += (v[i + 1] - v[i]);
		if(diff > maxLength)//맨 마지막부터 통나무 누적합이 최대길이보다 큰 경우 cut 갯수를 더한다. 
		{
			cnt++;
			diff = v[i + 1] - v[i];
			idx = i + 1;
		}
	}

	if(cnt < c)
	{
		idx = 1;
	}

	cout << maxLength << " " << v[idx];
}