BOJ 1114 - 통나무 자르기

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	2774	552	338	18.820%

문제

---

벌목꾼 백은진은 나무를 종이 공장에 옮겨야 한다. 하지만, 통나무의 길이가 너무 길어서 트럭에 들어가지 않으므로, 여러개의 조각으로 나눠야 한다.

통나무의 길이는 L cm이다. 그리고 통나무의 특정한 위치에서만 자를 수 있다. 통나무를 자를 수 있는 위치가 주어지고, 이때 이 위치는 통나무의 가장 왼쪽에서부터 떨어진 거리이다. 백은진은 많아야 C번 통나무를 자를 수 있다.

이때, 통나무의 가장 긴 조각을 작게 만드는 프로그램을 작성하시오.

입력

---

첫째 줄에 L, K와 C가 주어진다. L은 1,000,000,000보다 작거나 같은 자연수이고, K는 통나무를 자를 수 있는 위치의 개수이다. K와 C는 10,000보다 작거나 같은 자연수이다. 둘째 줄에 통나무를 자를 수 있는 위치가 주어진다.

출력

---

첫째 줄에 두 개의 수를 출력한다. 첫 번째 수는 가장 긴 조각의 길이이고, 두 번째 수는 그 때 처음 자르는 위치를 출력한다. 만약 가능한 것이 여러 가지라면, 처음 자르는 위치가 작은 것을 출력한다.

접근

---

나는 10억이 넘는 숫자를 보면 바로 이분 탐색이 떠오른다.
그래서 이분 탐색으로 끼워 맞춰봤는데, 될 것 같은 구현이 떠올랐다.

가장 긴 조각의 길이를 이분 탐색으로 구하면 될 것 같았다.
각 탐색에서는 mid 값을 길이로하면 C번 이하로 잘라도 되는지를 확인하면 된다.
C번을 초과하여 자르면 길이를 늘려주고, 반대인 경우 길이를 줄여주면 된다.
그리고 처음 자르는 위치가 가장 작게 하기 위해서 뒤에서부터 잘라준다.

풀이

---

1부터 L값까지를 기준으로 이분탐색을 해주었다.
arr에는 편의를 위해서 첫 인덱스에 0, 마지막 인덱스에 L을 추가했다.

각 탐색에서 사용되는 solve 함수에는, 잘라야 되는 cnt 값이 C 이하인지 반환한다.
여기서, cnt가 C보다 작을 경우에는 처음 자르는 위치를 첫번째 인덱스로 정해준다.
cnt는 sum 값을 기준으로 뒤에서부터 잘라야 되는 구간인지 확인한다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };

int L, K, C, answer, tmp, first, arr[10002];

bool solve(int len)
{
	int cnt = 0, sum = 0;
	tmp = -1;
	FDOWN(i, K - 1, 0)
	{
		if (sum + arr[i + 1] - arr[i] > len)
		{
			cnt++;
			sum = arr[i + 1] - arr[i];
			if (sum > len) return false;
			tmp = i + 1;
		}
		else
		{
			sum += arr[i + 1] - arr[i];
		}
	}
	if (cnt < C) tmp = 1;
	return cnt <= C;
}

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

	CIN3(L, K, C);
	arr[0] = 0, arr[K + 1] = L;
	FUP(i, 1, K) CIN(arr[i]);
	K++;
	sort(arr, arr + K);
	int l = 1, r = L;
	while (l <= r)
	{
		int mid = (l + r) / 2;
		if (solve(mid))
		{
			answer = mid;
			first = tmp;
			r = mid - 1;
		}
		else l = mid + 1;
	}
	COUT2(answer, arr[first]);


	return 0;
}