[백준 2805번] 나무자르기_C++ 이분탐색 & DP

문제 출처 :

www.acmicpc.net/problem/2805

2805번: 나무 자르기

 

일단 정답 코드는 아래와 같다.

틀렸던 코드와 원인 정리는 뒤에서 하겠다.

 

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

long long n, m, maxTree, h; vector<long long>v;
long long getM(int mid) {
	long long ans = 0;
	for (long long tree : v) {
		if (tree > mid) { //절단기보다 높으면
			ans += (tree - mid);
		}
	}
	return ans;
}
int main() {
	cin >> n >> m;
	for (long long i = 0; i < n; i++) {
		long long x; cin >> x;
		v.push_back(x);
		maxTree = max(maxTree, x);
	}
	long long preMid = 0;
	long long l = 0; long long r = maxTree;
	while (l <= r) {
		long long mid = (l + r) / 2;
		if (m <= getM(mid)) { //잘린 양을 줄여야 해. 즉 절단기를 높여야 해.
			h = mid;
			l = mid + 1;
		}
		else { //절단기를 낮춰야 해
			r = mid - 1;
		}
	}
	cout << h;
	return 0;
}

 

내가 틀렸던 원인:

 

1. m < getM일 때에도 mid 값을 저장했어야 했다.

 

아래의 반례를 생각해보자.

6 1

0 2 0 0 0 2

 

일반적인 이분탐색으로만 생각해서 m == getM일 때만 h = mid를 했었는데, m이랑 같은 경우를 찾지 못한 채 while문을 빠져나올 때가 있다. 그러면 h값은 변하는 거 없이 그냥 0이 나온다. 문제에서도 힌트가 있다. 적어도 m이라고 했으니 m보다 크게 가져갈 수도 있다는 의미이다. 그러므로 m < getM일 경우에도 mid 값을 저장해야 한다. 그래야 m과 같은 경우를 찾지 못한 채 while문을 빠져나왔을 때 제대로 된 최대 높이를 찾을 수 있다.

 

 

2.  이분탐색 left 값의 오류. left를 0이 아닌 들어온 나무 길이 중 최솟값으로 했었다.

 

아래의 반례를 생각해보자.

4 6

6 6 6 6

 

위읙 경우 m인 6보다 getM이 더 클 때의 최댓값을 찾아야 하므로 getM이 8이 되는 4가 답이다.

내 초기 코드처럼 left 값을 들어온 트리 중 최소길이로 하면 위의 예시에서 left와 right 모두가 6이 된다.

 

절단기 길이는 0부터 모든 가능한 값을 탐색해야 하므로 부적절하다.

 

수정했으면 좋았을 것들 :

 

1. 초기 코드에서는 algorithm헤더를 사용해서 정렬한 뒤 최댓값을 찾았었다. 그땐 left 값을 0이 아닌 배열의 최솟값으로 생각했어서 양쪽 모두를 구하기 위해 정렬을 했었는데, left는 0이어야 하므로 굳이 정렬할 필요가 없어진다. 그냥 right만 찾으면 되니까 max 메소드로 최댓값만 구하면 된다.

 

2. 전형적인 이분탐색 코드로 풀다보니 그냥 m과 getM의 리턴값을 비교할 때 세 가지로 나눠서 했었다. 같을 경우, m이 더 작을 경우, m이 더 클 경우. 그런데 이 문제에서는 m이랑 같지 않은데 while문을 빠져나올 경우가 있었으니 같을 경우나 m이 더 작을 경우나 둘이 똑같이 mid를 저장해야 한다. 즉 조건문을 굳이 세 개로 안하고 두 개로 했어도 됐다.