[알고리즘] 백준 2805번: 나무 자르기 (C++), 이분 탐색 (함수 없이 직접 구현)

이분 탐색 개념을 알고서도 이분 탐색 문제를 보면 '이게 왜 이분 탐색을 써야 되지?'라는 생각에 빠졌었다.

아무래도 '알고리즘 분류'에 들어가서 이분 탐색을 찾아 풀다 보니

'일단 이분 탐색을 써야 해'하는 전제를 두고서 들어갔기 때문에 쉽사리 문제에 접근할 수 없었다.

 

이분 탐색을 전제에 두지 않았다면 더 쉽게 접근할 수 있었을까

 

그랬다면 접근 방법은 이랬을 거다.

1. 제일 큰 나무 위에서 한 칸씩 줄여가며 자른 나무 개수 count
2. count가 >= M이 되는 시점에서 자른 높이 측정

생각보다 쉬운 접근이다.

---

이분 탐색이 필요했던 이유

문제를 보면 한 나무가 가질 수 있는 최대 높이가 1,000,000,000(10억)이라고 한다.

만약에 모든 나무를 끝까지 다 베어야 한다면 count는 10억 이상이 될 것이고,

제한 시간 1초를 가뿐히 넘어버릴 것이다.

 

하지만 높이를 구할 때 이분 탐색을 사용하여 높이가 가질 수 있는 최댓값을 구하는 것은 가능하다.

시간 복잡도도 O(log N) = 29.90... 의 시간 복잡도를 가지기 때문에 가능하다.

 

즉, 높이가 가질 수 있는 범위(0 ~ 1,000,000,000)에서 이분 탐색을 하여 범위를 좁혀나가면서

최댓값을 찾는 게 가능하다는 소리다.

 

이 문제에서는 binary_search 함수를 쓸 수 없었다. 이분 탐색을 통해 '특정한 값'이 무엇인지 찾아야 하는데

binary_search함수는 '특정한 값'이 무엇인지 알고서 이 값이 어떠한 자료구조에 안에 있는지 확인차 사용하는 것이기 때문이다.

---

코드 해설

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

int main() {
	long long int n, m;
	cin >> n >> m;
	vector<long long int> tree;
	for (int i = 0; i < n; i++) {
		long long int a;
		cin >> a;
		tree.push_back(a);
	}

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

	long long int low = 0;
	long long int high = tree[tree.size() - 1];

	long long int sum = 0;

	while (low + 1 < high) {
		long long int mid = (low + high) / 2;
		sum = 0;
		for (int i = 0; i < tree.size(); i++) {
			if (tree[i] > mid) {
				sum += tree[i] - mid;
			}
		}
		//cout << mid << ' ' << sum << '\n';

		if (sum < m) {
			high = mid;
		}
		else {
			low = mid;
		}
	}

	cout << low;
	return 0;
}

 

1. n과 m 그리고, 나무가 가질 수 있는 높이 a 모두 엄청 큰 수이기 때문에 long long int 자료형으로 변수를 선언했다.

 

2. 정렬을 통해 맨 마지막 원소가 제일 높은 나무가 되도록 코딩하여 high에 이를 할당에 주었다.

 

3. sum은 자른 나무들의 길이를 모두 합한 변수이다.

 

4. sum이 요구되는 길이보다 작다면 더 잘라야 한다는 뜻이기 때문에 high에 현재 mid를 할당하고 더 자르게 해 주었다.

4.2 low에서는 이와 반대로 높이를 만족하거나 sum이 요구되는 길이보다 많기 때문에 자르는 길이를 줄여도 된다는 뜻이다. (문제에서는 자를 수 있는 높이의 최댓값을 요구한다. == 위에서 잘라가고 있기 때문에 최대한 적게 잘라야 높이를 만족할 수 있다.)

 

5. 반환되어야 하는 게 왜 low인가, while의 조건은 왜 (low + 1 < high)인가?

---

반환되어야 하는 게 왜 low인가, while의 조건은 왜 (low + 1 < high)인가?

사실 이 문제를 풀면서 제일 궁금했던 부분이다.

왜 반환되어야 하는 게 low일까, 조건은 왜 (low + 1 < high) 여야 할까.

이 부분에서 막혀서 문제를 여러 번 틀렸었기 때문이다.

 

예제 1에서 while 반복문이 한 번 돌 때마다 cout << low << ' ' << high << ' ' << mid << ' ' << sum << '\n';을 통해 각각 어떤 값을 갖는지 출력해보았다.

cout << low << ' ' << high << ' ' << mid << ' ' << sum << '\n';
  0 20 10 22
10 20 15   7
15 20 17   3
15 17 16   5
(보기에 편하기 위해 일의 자리 앞은 두 칸 띄웠다.)

cout << low;
15

주관적으로 해석했을 때는 이런 결론이 나왔다.

 

mid가 15일 때, while안에 else 조건문을 만족한다.

	while (low + 1 < high) {
		long long int mid = (low + high) / 2;
		sum = 0;
		for (int i = 0; i < tree.size(); i++) {
			if (tree[i] > mid) {
				sum += tree[i] - mid;
			}
		}
		//cout << mid << ' ' << sum << '\n';

		if (sum < m) {
			high = mid;
		}
		else { // <<- 이 부분을 만족함
			low = mid;
		}
	}

그래서 mid가 low에 할당이 되게 되는데

그럼에도 불구하고, 이진 탐색이 끝날 때까지 low가 다른 mid로 할당되지 않은 이유는

그다음 while문에서 mid는 적어도 가져야 할 나무의 개수(sum)를 구하는데에서 m보다 계속 적게 나오기 때문이다.

즉, 이미 15일 때가 최대였음을 알 수 있다.

 

else가 어떤 조건을 가지고 있는지 그리고 이진 탐색이 어떻게 끝나는지 이진 탐색의 끝이 결과에 영향을 미치는지 아닌지를 알 수 있었어야 했다.

 

그래서 궁금증이 생겼었는데

sum == m일 때의 조건을 따로 빼두고 다른 변수에 이때 mid값을 할당하면 되지 않을까?

왜냐하면 따로 조건을 빼두면 보기에도 편할 거 같았기 때문이다.

코드로 표현하면 이랬다.

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

int main() {
	long long int n, m;
	cin >> n >> m;
	vector<long long int> tree;
	for (int i = 0; i < n; i++) {
		long long int a;
		cin >> a;
		tree.push_back(a);
	}

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

	long long int low = 0;
	long long int high = tree[tree.size() - 1];

	long long int sum = 0;
	long long int answer = 0;

	while (low + 1 < high) {
		long long int mid = (low + high) / 2;
		sum = 0;
		for (int i = 0; i < tree.size(); i++) {
			if (tree[i] > mid) {
				sum += tree[i] - mid;
			}
		}
		//cout << mid << ' ' << sum << '\n';
		//cout << low << ' ' << high << ' ' << mid << ' ' << sum << '\n';

		if (sum < m) {
			high = mid;
		}
		else if (sum > m){
			low = mid;
		}
		else if (sum == m) {
			low = mid;
			answer = mid;
		}
	}

	cout << answer;
	return 0;
}

즉, answer에 답을 담고자 했는데 이는 오류를 불러일으킨다.

그래서 반례를 찾던 도중 이러한 반례를 찾았다.

2 11
10 10
정답: 4

저 코드로 이 예시를 돌려봤는데 answer가 0으로 출력되었었다.

다시 cout << low << ' ' << high << ' ' << mid << ' ' << sum << '\n'; 를 사용했었는데

cout << low << ' ' << high << ' ' << mid << ' ' << sum << '\n'; 
0 10  5 10
0   5  2 16
2   5  3 14
3   5  4 12
(마지막 조건문에서 4가 mid에서 low로 할당된다.)

cout << answer;
0

실제 정답: 4

answer에 아무것도 반환되지 않았던(초기값이 0 그대로여서) 이유는 sum과 m이 같았던 순간이 없었기 때문이다.

애초에 문제에서 가질 수 있는 높이의 최댓값을 요구했기 때문이다.

즉, 이진 탐색이 끝났을 때 그나마 최대로 가질 수 있었던 값을 찾을 수 있었다.

 

이번 문제는 이분 탐색이 돌아가는 원리는 이해하고 있었지만 while안의 조건문의 역할을 알 수 있게 해 주었다.

처음엔 그냥 값보다 작으니까 low에 mid를 할당하거나 그저 이런 단일적인 기능만 한다고 생각했었다.

하지만, 제일 중요했고, 이해가 제일 필요했던 조건문이었다.