[백준/C++] 2805번 나무자르기 / 이분탐색/ binary search - (1)

백준 2805번 나무자르기

 

이분 탐색은 조건을 잘 못 짤시에 무한루프에 빠져 시간 초과가 뜨는 경우가 많다.

이렇게 빠지지 않을려면 조건을 잘 세워야한다.

 

주어진 문제에 조건은

1. 나무의 높이 정하기 ( 여기서 주의해야할 점은 m은 적어도 이정도지 무조건 m개는 아니다!!)

2. 나무의 높이를 기준으로 이분탐색 하기

 

long long st = maxx;
long long en = 0;

int ans = 0;

while (en<= st) {
	long long result = 0;
	long long mid = (st + en) / 2;

	for (int i = 0; i < n; i++) {
		long num = 0;
		num = vec[i] - mid;
		if (num > 0) result += num;
	}

 

보이는 바와 같이 st가 max면 나무를 짜르는 총 max 값은 0이다. 따라서 en을 0이라고 설정하여 잘랐을 때 나무 길이의 총값으로 st와 en을 정해줬다.

 

		if (result > m) {
			en = mid + 1;
		}
		else if (result <= m) {
			st = mid - 1;
			ans = st;
			if (result == m) {
				cout << mid;
				return;
			}
		}
	}

 

result (나무 자르는 총 값)이 m보다 클 때는 덜 잘라야하니깐 en을 mid + 1로 변경

result 값이 m 보다 작은 경우는 st값을 mid - 1로 변경하고, 값이 같을 때는 빠져나오게 했다. 이렇게 짜준 이유는 나무 길이가 '적어도' m과 같거나 커야하기 때문에 딱 맞게 짜르지 못했을 경우를 대비해 저렇게 나온 것이다. 

 

---

2805번 나무자르기 전체 코드 

#include<iostream>
#include<vector>

using namespace std;

vector<long long> vec;
int n;
long long m;
long long maxx = 0;
int minn = 0;

void bina(int a) {

	long long st = maxx;
	long long en = 0;

	int ans = 0;

	while (en<= st) {
		long long result = 0;
		long long mid = (st + en) / 2;

		for (int i = 0; i < n; i++) {
			long num = 0;
			num = vec[i] - mid;
			if (num > 0) result += num;
		}

		/*if (result == m) {
			cout << mid;
			return;
		}*/

		if (result > m) {
			en = mid + 1;
		}
		else if (result <= m) {
			st = mid - 1;
			ans = st;
			if (result == m) {
				cout << mid;
				return;
			}
		}
	}
	//cout << "st : " << st << " en : " << en;
	cout << ans;
}

int main() {
	
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		long long num;
		cin >> num;
		vec.push_back(num);
		if (num > maxx) maxx = num;
	}
	//cout << maxx;
	bina(m);
}